看了这篇博文，总算是把Trie图弄明白了
Runtime Error了无数次，一直不知道为什么，于是写了个脚本生成了一组大数据，发现果然段错误了。
调试了一下午，总算闹明白了，为什么呢？
1. 空间超大的变量不要放在函数里，会爆栈，应该弄成全局变量或者是从堆上动态分配。
2. 看清题目的数据范围，一开始我的MAX_NODE设的是1024。。。
代码：
#include <iostream>
#include <cstring> using namespace std; #define MAX_NODE 1000010
#define SIGMA_SIZE 32 int q[MAX_NODE]; struct TrieGraph {
int f[MAX_NODE];
int g[MAX_NODE][SIGMA_SIZE];
int m[MAX_NODE];
int size; void init() {
size = ;
memset(f, , sizeof(f));
memset(g[], , sizeof(g[]));
} int index(char c) {
return c - 'a';
} void insert(const char *s) {
int u = ;
while (*s) {
int i = index(*s);
if (!g[u][i]) {
memset(g[size], , sizeof(g[size]));
m[size] = ;
g[u][i] = size++;
}
u = g[u][i];
s++;
}
m[u] = ;
} void build() {
int qh = , qt = ;
f[] = ;
for (int i = ; i < ; i++) {
int &p = g[][i];
if (p) {
f[p] = ;
q[qt++] = p;
}
else
p = ;
}
while (qh < qt) {
int u = q[qh++];
for (int i = ; i < ; i++) {
int &v = g[u][i];
if (v) {
q[qt++] = v;
f[v] = g[f[u]][i];
m[u] |= m[f[u]];
}
else
v = g[f[u]][i];
}
}
} bool find(const char *s) {
int u = ;
while (*s) {
int i = index(*s);
while (u && !g[u][i])
u = f[u];
u = g[u][i];
if (m[u])
return true;
s++;
}
return false;
}
} tg; int main() {
int N;
string s; tg.init();
cin >> N;
for (int i = ; i < N; i++) {
cin >> s;
tg.insert(s.c_str());
}
tg.build();
cin >> s;
cout << (tg.find(s.c_str()) ? "YES" : "NO") << endl;
return ;
}