AC自动机板子

· · 题解

AC自动机博客介绍

oiwiki介绍

AC自动机模板题（已过lg）

AC自动机模板题（已过df）

未优化

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e6+10,L=55;
int ch[N*L][26],cnt[N*L],idx;
int ne[N*L];//每个结点对应的next值 
int q[N*L];//队列 
char w[L],s[M];//w 单词 s 文章 
int T,n;
void init(){//清空 
    memset(ch,0,sizeof(ch));
    memset(cnt,0,sizeof(cnt));
    idx=0;
    memset(ne,0,sizeof(ne));
}
void insert(char w[]){//建树 
    int p=0;//从根开始 
    for(int i=0;w[i];i++){
        int x=w[i]-'a';
        if(!ch[p][x])ch[p][x]=++idx;
        p=ch[p][x];
    }
    cnt[p]++;//以当前结点结束的单词数加一 
}
void bfs(){//求每个结点的next值 
    int h=1,t=0;//默认为空
    //将根节点下面的第一层结点入队  因为这一层结点next值都为0
    for(int i=0;i<26;i++){
        if(ch[0][i])q[++t]=ch[0][i];
    }
    //广搜计算每一层结点next值
    while(h<=t){
        int f=q[h];//上一层父结点编号 
        for(int i=0;i<26;i++){
            if(ch[f][i]){
                int c=ch[f][i];//子结点编号 
                int j=ne[f];//父结点next值
                while(j&&!ch[j][i]){
                    j=ne[j];
                }
                if(ch[j][i]){
                    j=ch[j][i];
                }
                ne[c]=j;
                q[++t]=c;//入队 
            }
        }
        h++;//出队 
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        while(n--){
            scanf("%s",w);
            insert(w);
        }//建树 
        bfs();//求每个结点的next值 
        scanf("%s",s);
        int res=0;
        for(int i=0,j=0;s[i];i++){//i 遍历s字符串   
                                  //j 字典树从根开始遍历 
            int x=s[i]-'a';
            //匹配不上j回跳 
            while(j&&!ch[j][x])j=ne[j];
            if(ch[j][x])j=ch[j][x];//能匹配 j跳子结点 
            int p=j;
            while(p!=0){
                res+=cnt[p];
                cnt[p]=0;
                p=ne[p];//看以当前单词后缀为前缀单词是否存在 
            }
        }
        printf("%d\n",res);
    }

    return 0;
}

优化回调，线性时间版本

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10,M=1e6+10,L=55;
int ch[N*L][26],cnt[N*L],idx;
int ne[N*L];//每个结点对应的next值 
int q[N*L];//队列 
char w[L],s[M];//w 单词 s 文章 
int T,n;
void init(){//清空 
    memset(ch,0,sizeof(ch));
    memset(cnt,0,sizeof(cnt));
    idx=0;
    memset(ne,0,sizeof(ne));
}
void insert(char w[]){//建树 
    int p=0;//从根开始 
    for(int i=0;w[i];i++){
        int x=w[i]-'a';
        if(!ch[p][x])ch[p][x]=++idx;
        p=ch[p][x];
    }
    cnt[p]++;//以当前结点结束的单词数加一 
}
//void bfs(){//求每个结点的next值 
//  int h=1,t=0;//默认为空
//  //将根节点下面的第一层结点入队  因为这一层结点next值都为0
//  for(int i=0;i<26;i++){
//      if(ch[0][i])q[++t]=ch[0][i];
//  }
//  //广搜计算每一层结点next值
//  while(h<=t){
//      int f=q[h];//上一层父结点编号 
//      for(int i=0;i<26;i++){
//          if(ch[f][i]){
//              int c=ch[f][i];//子结点编号 
//              int j=ne[f];//父结点next值
//              while(j&&!ch[j][i]){
//                  j=ne[j];
//              }
//              if(ch[j][i]){
//                  j=ch[j][i];
//              }
//              ne[c]=j;
//              q[++t]=c;//入队 
//          }
//      }
//      h++;//出队 
//  }
//}
void bfs(){
    int h=1,t=0;//默认为空
    //将根节点下面的第一层结点入队  因为这一层结点next值都为0
    for(int i=0;i<26;i++){
        if(ch[0][i])q[++t]=ch[0][i];
    }
    //广搜计算每一层结点next值
    while(h<=t){
        int f=q[h];//上一层父结点编号 
        for(int i=0;i<26;i++){
            if(ch[f][i]){
                int c=ch[f][i];//子结点编号 
                //父结点next值 
                ne[c]=ch[ne[f]][i];
                q[++t]=c;//入队 
            }
            else{
                //如果结点f不存在子结点i 存储假设存在结点i，其next值是多少 
                ch[f][i]=ch[ne[f]][i];
            }
        }
        h++;//出队 
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
//  scanf("%d",&T);
//  while(T--){
        init();
        scanf("%d",&n);
        while(n--){
            scanf("%s",w);
            insert(w);
        }//建树 
        bfs();//求每个结点的next值 
        scanf("%s",s);
        int res=0;
        for(int i=0,j=0;s[i];i++){//i 遍历s字符串   
                                  //j 字典树从根开始遍历 
            int x=s[i]-'a';
            //匹配不上j回跳 
            while(j&&!ch[j][x])j=ne[j];
            if(ch[j][x])j=ch[j][x];//能匹配 j跳子结点 
            int p=j;
            while(p!=0){
                res+=cnt[p];
                cnt[p]=0;
                p=ne[p];//看以当前单词后缀为前缀单词是否存在 
            }
        }
        printf("%d\n",res);
//  }

    return 0;
}