HDU_2222
今天开始学AC自动机了，这个就是我AC自动机的处女作了。这个题有个小trick就是单词列表中可能有重复的单词，但这些重复的单词应看做不同的，因此建字典树时做标记的时候，把原来的赋值为1的操作变为自加1的操作即可。
最后匹配的时候有一个小优化，就是比如当前正在看有多少个以j结点的字符为结尾的单词，那么我们还需要不停地沿预处理的标记向上找，当我们找过之后就可以把当前节点的标记做成-1，以后再遇到-1的时候，就直接break，无需再沿着标记向上找了，因为上面的结点一定在之前就找过了。这个优化大概能节省400ms的时间。
#include<stdio.h>
#include<string.h>
#define MAXD 500010
#define MAXT 1000010
char b[60], txt[MAXT];
int N, next[MAXD][26], flag[MAXD], P[MAXD], q[MAXD], e, cnt;
void insert(int cur, int k)
{
++ e;
flag[e] = 0;
memset(next[e], 0, sizeof(next[e]));
next[cur][k] = e;
}
void init()
{
int i, j, k, cur;
scanf("%d", &N);
e = 0;
memset(next[e], 0, sizeof(next[e]));
for(i = 0; i < N; i ++)
{
scanf("%s", b);
cur = 0;
for(j = 0; b[j]; j ++)
{
k = b[j] - 'a';
if(!next[cur][k])
insert(cur, k);
cur = next[cur][k];
}
++ flag[cur];
}
}
void prepare()
{
int i, j, k, u, x, front, rear;
front = rear = 0;
P[0] = q[rear ++] = 0;
while(front < rear)
{
u = q[front ++];
for(i = 0; i < 26; i ++)
if(next[u][i])
{
x = next[u][i];
if(u == 0)
P[x] = 0;
else
{
for(j = P[u]; j != 0; j = P[j])
if(next[j][i])
{
P[x] = next[j][i];
break;
}
if(j == 0)
P[x] = next[0][i];
}
q[rear ++] = next[u][i];
}
}
}
void solve()
{
int i, j, k, t;
prepare();
scanf("%s", txt);
j = cnt = 0;
for(i = 0; txt[i]; i ++)
{
k = txt[i] - 'a';
while(j > 0 && !next[j][k])
j = P[j];
j = next[j][k];
for(t = j; t > 0; t = P[t])
{
if(flag[t] >= 0)
{
cnt += flag[t];
flag[t] = -1;
}
else
break;
}
}
printf("%d\n", cnt);
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
init();
solve();
}
return 0;
}