我会五种自动机：
WA自动机，TLE自动机，RE自动机，CE自动机和UKE自动机，就是不会AC自动机

问题：给出 $M$ 个模式串 $P_i$，问有多少个模式串在字符串 $S$ 中出现过。

P1 = a
P2 = ab

S = abc

暴力算法：每个模式串都建 $next$ 数组，都和 $S$ 匹配一次 $O(M(|S|+|P|))$
每个模式串都使用 $KMP$ 进行匹配的话，太慢了

考虑将模式串都组合在一起，建立 “$next$ 数组”

fail 指针

先将所有模式串建成一颗 $Trie$ 树

$\operatorname{KMP} \ next$ 数组：对于字符串 $P$ 的前 $i$ 个字符构成的子串既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 next[i]

$\operatorname{fail}$ 指针：每个节点的 $\operatorname{fail}$ 指针指向 $Trie$ 树上该节点所代表字符串的最长后缀节点

使用 $\operatorname{BFS}$ 逐层构建 $\operatorname{fail}$ 指针

代码实现

// 插入 Trie 树
for (int i = 1; i <= n; ++i) {
    cin >> s;
    int x = 0;
    for (int j = 0; s[j]; ++j) {
        if (!ch[x][s[j]-'A']) ch[x][s[j]-'A'] = tot++;
        x = ch[x][s[j]-'A'];
    }
    cnt[x] += 1;
}

// BFS 遍历求 next 指针
int s = 0, e = 1;
q[0] = next[0] = 0;
while (s < e) {
    int x = q[s++];
    for (int j = 0; j < 26; ++j) {
        if (ch[x][j]) {
            q[e++] = ch[x][j];
            next[ch[x]][j] = (!x)?0:ch[next[x]][j];
        }
        else {
            ch[x][j] = ch[next[x]][j];
        }
    }
}

查询一个串 s 里出现了几次模板串

int x = 0, res = 0;
for (int i = 0; s[i]; ++i) {
    res += cnt[x];
    x = ch[x][s[i]-'A'];
}

因为 ch[x] 已经把所有的 $26$ 种可能的转移都处理好了。