AcWing 算法提高课 AC自动机

AC自动机=Trie+kmp

优化：Trie图

1、kmp

长字符串s和模板串p都以下标1开始。

(1) 求next数组：kmp的next数组存的是p的自匹配，即以p[i]为结尾的后缀能够匹配的最长非平凡(不是自身)前缀。由于非平凡，next[0]=next[1]=0，循环从2开始。

(2)进行匹配，将模板串p在长字符串s上移动，并求出当前可以匹配的最长长度，如果此长度为p的长度，则匹配成功。循环从1开始（可能p长度为1并且直接匹配成功 ）

例题：https://www.acwing.com/blog/content/404/

模板：统计模板串在长字符串中出现的个数

int n;
const int N=10010;
const int S=55,M=1000010;

int tr[N*S][26];//自动机数组，第一维节点，第二维子节点
int cnt[N*S];//以当前节点结尾的单词数量
int idx;

char str[M];
int que[N*S];
int 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])
            que[++tt]=tr[0][i];
    }
    while(hh<=tt)
    {
        int t=que[hh++];
        for(int i=0;i<26;i++)
        {
            int c=tr[t][i];
            if(!c) continue;
            int j=ne[t];
            while(j&&!tr[j][i]) j=ne[j];
            if(tr[j][i]) j=tr[j][i];
            ne[c]=j;
            que[++tt]=c;
        }
    }
}
void YD()
{
    memset(tr,0,sizeof(tr));
    memset(cnt,0,sizeof(cnt));
    memset(ne,0,sizeof(ne));
    idx=0;
    cin>>n;
    while(n--)
    {
        cin>>(str);
        Insert();//trie插入
    }
    Build();//构建ac自动机
    
    cin>>str;
    int res=0;
    for(int i=0,j=0;str[i];i++)
    {
        int t=str[i]-'a';
        while(j&&!tr[j][t]) j=ne[j];
        if(tr[j][t]) j=tr[j][t];
        //统计答案不光要统计j 还要统计更短的可能出现的单词，即往ne[j]去查询
        
        int p=j;
        while(p)
        {
            res+=cnt[p];
            cnt[p]=0;
            p=ne[p];
        }
        
    }
    cout<<res<<endl;
}