> 形式上，AC 自动机基于由若干模式串构成的 Trie 树，并在此之上增加了一些 fail 边；本质上，**AC 自动机是一个关于若干模式串的 DFA（确定有限状态自动机），接受且仅接受以某一个模式串作为后缀的字符串。**
>
> 并且，与一般自动机不同的，AC 自动机还有 **关于某个模式串的接受状态**（我自己起的名字..），也就是与某个模式串匹配（以某个模式串为后缀）的那些状态，即某个模式串在 Trie 树上的终止节点在 fail 树上的整个子树。
这段话我先放上来，因为我相信绝大部分人学了 AC 自动机之后甚至不知道 AC 自动机是什么，而只知道它有什么用。
这篇题解假定你会 AC 自动机，如果不会的话，可以看[我写的教程](https://ouuan.github.io/AC自动机学习笔记)。
然后的话，很多人用 AC 自动机进行多模匹配时都会暴力跳 fail 边，但这样做复杂度是错误的，可以被类似于 `aaaaa……aaaaa` 这样的串卡掉。
正确的做法是建出 fail 树，记录自动机上的每个状态被匹配了几次，最后求出每个模式串在 Trie 上的终止节点在 fail 树上的子树总匹配次数就可以了。
参考代码：
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 200010;
const int T = 200010;
const int S = 2000010;
void dfs(int u);
void add(int u, int v);
char s[S];
queue<int> q;
int head[T], nxt[T], to[T], cnt;
int n, tr[T][26], fail[T], tot = 1, match[N], siz[T];
int main()
{
int i, j, u;
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%s", s);
for (u = 1, j = 0; s[j]; ++j)
{
int c = s[j] - 'a';
if (!tr[u][c]) tr[u][c] = ++tot;
u = tr[u][c];
}
match[i] = u; // 记录每个模式串在 Trie 树上的终止节点
}
for (i = 0; i < 26; ++i) tr[0][i] = 1; // 一种比较与众不同（个人认为比较正确）的 AC 自动机建法，详见上文提到的我写的博客
q.push(1);
while (!q.empty())
{
u = q.front();
q.pop();
for (i = 0; i < 26; ++i)
{
if (tr[u][i])
{
fail[tr[u][i]] = tr[fail[u]][i];
q.push(tr[u][i]);
}
else tr[u][i] = tr[fail[u]][i];
}
}
scanf("%s", s);
for (u = 1, i = 0; s[i]; ++i)
{
u = tr[u][s[i] - 'a'];
++siz[u]; // 记录匹配次数
}
for (i = 2; i <= tot; ++i) add(fail[i], i); // 建 fail 树
dfs(1); // 统计子树和
for (i = 1; i <= n; ++i) printf("%d\n", siz[match[i]]);
return 0;
}
void dfs(int u)
{
int i, v;
for (i = head[u]; i; i = nxt[i])
{
v = to[i];
dfs(v);
siz[u] += siz[v];
}
}
void add(int u, int v)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}
```