AC自动机
Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。
要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字
符串），所以经常被搜索引擎系统用于文本词频统计。
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];
void insert()
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int t = str[i] - 'a';
if (!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];
}
cnt[p] ++ ;
}
void build()
{
int hh = 0, tt = -1;
for (int i = 0; i < 26; i ++ )
if (tr[0][i])
q[ ++ tt] = tr[0][i];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = 0; i < 26; i ++ )
{
int p = tr[t][i];
if (!p) tr[t][i] = tr[ne[t]][i];
else
{
ne[p] = tr[ne[t]][i];
q[ ++ tt] = p;
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
memset(tr, 0, sizeof tr);
memset(cnt, 0, sizeof cnt);
memset(ne, 0, sizeof ne);
idx = 0;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%s", str);
insert();
}
build();
scanf("%s", str);
int res = 0;
for (int i = 0, j = 0; str[i]; i ++ )
{
int t = str[i] - 'a';
j = tr[j][t];
int p = j;
while (p)
{
res += cnt[p];
cnt[p] = 0;
p = ne[p];
}
}
printf("%d\n", res);
}
return 0;
}