【UOJ #13】【UER #1】跳蚤OS

http://uoj.ac/problem/13
建立trie树，然后建立go指针，
和AC自动机里的fail指针差不多，
走到一个快捷方式就从go指针走。
注意在trie树上要保留字符'/'，不能用end标记来标识一个字符串的结束。
因为可能出现"/Iam/zz"和"/Iamzz"这两种情况，如果只用end标记，tire树上这两个字符串就会共用一条路径。
(总之是蒟蒻才会犯的错误，神犇们勿喷_(:з」∠)_)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int in() {
int k = 0; char c = getchar();
for(; c < '0' || c > '9'; c = getchar());
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k;
}
struct State {
int num;
State *nxt[27], *go, *fa;
State(State *_fa, int _num) {
memset(nxt, 0, sizeof(nxt));
go = 0; fa = _fa; num = _num;
}
} *root;
State *to(char *c) {
int len = strlen(c), x;
if (len == 1 && c[0] == '/') return root;
State *tmp = root;
for(int i = 0; i < len; ++i) {
if (c[i] == '/') x = 26;
else x = c[i] - 'a';
if (tmp->nxt[x] == 0)
tmp->nxt[x] = new State(tmp, x);
tmp = tmp->nxt[x];
if ((c[i + 1] == '' || c[i + 1] == '/') && tmp->go)
tmp = tmp->go;
}
return tmp;
}
char s[500003], t[500003];
void print(State *tmp) {
int tot = 0;
if (tmp == root) {puts("/"); return;}
while (tmp != root) {
if (tmp->num <= 25) t[++tot] = 'a' + tmp->num;
else t[++tot] = '/';
tmp = tmp->fa;
}
while (tot) putchar(t[tot--]);
puts("");
}
int n, m;
int main() {
root = new State(0, 0);
n = in(); m = in();
for(int i = 1; i <= n; ++i) {
scanf("%s", s); scanf("%s", t);
to(s)->go = to(t);
}
for(int i = 1; i <= m; ++i) {
scanf("%s", s);
print(to(s));
}
return 0;
}