AC自动机

全称Aho–Corasick自动机（而不是Accepted自动机）

用于在O(n)的时间复杂度内求出若干个单词出现的位置、次数

首先将众多单词存起来

相信大家都记得trie树

这颗trie树中有she、he、say三个单词

考虑用类似KMP的方式处理这棵树

ne[i]代表根到i节点的路径构成的字符串的最长“后缀的相同前缀”（有点绕）

例如she的h的ne是he的h，she的e的ne是he的e

每个点的ne都一定比自己层数低，所以求ne可以使用层序遍历，也就是广搜

这样求到i时i的父亲一定已经求过了

可以学习KMP，从父节点的ne开始往后跳

while(hh<=tt){
    int t=q[hh++];  //取出队头
    for(int i=0;i<26;i++)  //26个字母
        if(tr[t][i]){
            int p=tr[t][i];
            int j=ne[t] //父节点的ne
            while(j&&!tr[j][i]) //没找到就一直往后跳
                j=ne[j];
            if(tr[j][i])    //找到了要前进一步
                j=tr[j][i];
            ne[p]=j;
            q[++tt]=p;
        }
}

例如求she的e的ne时j是这么跳的

这样做的时间复杂度是O(nlogn)

trie图优化

上文做法带log的原因是每次j期望要跳logn次

但每次跳的路径都是高度重叠的，从j出发往后跳一定会跳到ne[j]

而且从j往后跳一定是因为j没有对应要求的字母的儿子

只要将j的空儿子指向ne[j]的相同字母儿子，问题就解决了！

he的h没有y儿子，空儿子指向h的ne也就是0的y儿子

0也没有y儿子，he的h的y儿子赋值为0

求shy的y时ne一定等于shy的h的ne的y儿子，也就是0

一步到位

inline 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++){  //26个字母
            int p=tr[t][i];
            if(!p)  //空儿子指向ne[t]的同字母儿子
                tr[t][i]=tr[ne[t]][i];
            else{
                ne[p]=tr[ne[t]][i]; //通过一长串赋值直接求出ne
                q[++tt]=p;
            }
        }
    }
}

对比母串

和KMP类似，匹配不上就往后跳

但因为上文的trie图优化，遇到空儿子会自动跳到下一个能匹配上的位置

所以只需要每次走到对应字母的儿子即可

for(int i=0,j=0;str[i];i++){
    int t=str[i]-'a';
    j=tr[j][t]; //走到对应字母的儿子
    int p=j;
    while(p){   //因为可能出现多个单词，需要一直跳直到p=0也就是不再有单词
        ans+=cnt[p];    //统计答案
        cnt[p]=0;   //只记一次，清空统计过的节点
        p=ne[p];    //往后跳
    }
}

完整代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=10010,S=55,M=1000010;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],ne[N*S];
inline void insert(){   //trie树加入单词
    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]++;
}
inline 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;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){   //建trie树
            scanf("%s",str);
            insert();
        }
        build();    //求出每个节点的ne
        scanf("%s",str);
        int ans=0;
        for(int i=0,j=0;str[i];i++){    //对比母串
            int t=str[i]-'a';
            j=tr[j][t];
            int p=j;
            while(p){
                ans+=cnt[p];
                cnt[p]=0;
                p=ne[p];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}