AC自动机模板

P3808 【模板】AC 自动机

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;

int ch[M][26],cnt[M],fail[M],tot;
void insert(char *s) {//字典树的建立
    int p=0,len=strlen(s+1);
    for(int i=1;i<=len;i++) {
        int v=s[i]-'a';
        if(ch[p][v]==0)ch[p][v]=++tot;
        p=ch[p][v];
    }
    cnt[p]++;
}

void init() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(ch[0][i])q.push(ch[0][i]);//对于第一层的点之间遍历
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++) {
            if(ch[now][i]) {
                fail[ch[now][i]]=ch[fail[now]][i];//找失落点
                q.push(ch[now][i]);
            }
            else ch[now][i]=ch[fail[now]][i];//继承上一个点的状态
        }
    }
}

int query(char *s) {
    int len=strlen(s+1);
    int now=0,ans=0;
    for(int i=1;i<=len;i++) {//从起点开始遍历
        now=ch[now][s[i]-'a'];
        for(int j=now;j&&cnt[j]!=-1;j=fail[j]) {
            ans+=cnt[j];
            cnt[j]=-1;//防止一个点重复遍历
        }
    }
    return ans;
}

char s[M];
int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        insert(s);
    }//建树
    init();
    scanf("%s",s+1);
    cout<<query(s)<<endl;//查找
    return 0;
}