AC自动机专题

先开个坑

按照惯例，先来模板

就以hdu2222的代码作为模板吧，就是在字典树上连上一些失配边，这个模板将不存在的子结点直接当成失配边连到根，对所有的转移都一视同仁。失配时候的转移和kmp是一样的道理，只是kmp是在链上转移，而自动机是在树上转移。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=500100;struct Trie{ int ch[maxn][26],end[maxn]; int f[maxn]; int rt,L; int newnode() { memset(ch[L],-1,sizeof(ch[L])); end[L]=0; return L++; } void init() { L=0; rt=newnode(); } void insert(char *s) { int u=rt; int len=strlen(s); for(int i=0;i

q; f[rt]=rt; for(int c=0;c<26;c++){ if(ch[rt][c]==-1) ch[rt][c]=rt; else{ f[ch[rt][c]]=rt; q.push(ch[rt][c]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int c=0;c<26;c++){ if(ch[u][c]==-1) ch[u][c]=ch[f[u]][c]; else{ f[ch[u][c]]=ch[f[u]][c]; q.push(ch[u][c]); } } } } int find(char *s) { int len=strlen(s); int u=rt; int res=0; for(int i=0;i

>T; while(T--){ ac.init(); scanf("%d",&n); while(n--){ scanf("%s",s); ac.insert(s); } ac.build(); scanf("%s",s); printf("%d\n",ac.find(s)); } return 0;}

View Code

hdu2222： Keywords Search

第一道AC自动机，最简单的模板题。每走一个字符就按失配边走到根，把沿途经过的字符串个数记录下来并将其设为0（也就是统计。。。。。。）。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int maxn=500100;struct Trie{ int ch[maxn][26],end[maxn]; int f[maxn]; int rt,L; int newnode() { memset(ch[L],-1,sizeof(ch[L])); end[L]=0; return L++; } void init() { L=0; rt=newnode(); } void insert(char *s) { int u=rt; int len=strlen(s); for(int i=0;i

>T; while(T--){ ac.init(); scanf("%d",&n); while(n--){ scanf("%s",s); ac.insert(s); } ac.build(); scanf("%s",s); printf("%d\n",ac.find(s)); } return 0;}

View Code

hdu2896：病毒侵袭

很简单，开个vector记录id，直接匹配就行了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn=80010;const int SIZE=128;int N,M;char s[maxn];set
              
                ans;struct Trie{ int ch[maxn][SIZE],f[maxn]; vector
               
                 id[maxn]; int rt,L; int newnode() { memset(ch[L],-1,sizeof(ch[L])); id[L].clear(); return L++; } void init() { for(int i=0;i

q; f[rt]=rt; for(int c=0;c

>N){ ac.init(); for(int i=1;i<=N;i++){ scanf("%s",s); ac.insert(s,i); } ac.build(); cin>>M; int cnt=0; for(int i=1;i<=M;i++){ scanf("%s",s); ans.clear(); ac.find(s); if((int)ans.size()>0){ printf("web %d:",i); for(set

::iterator it=ans.begin();it!=ans.end();++it) printf(" %d",*it); puts(""); cnt++; } } printf("total: %d\n",cnt); } return 0;}

View Code

hdu3065：病毒侵袭持续中

很简单的题。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int maxn=2000100;const int N=1100;const int maxm=500100;char s[maxn];int n;char t[N][60];int cnt[N];struct Trie{ int ch[maxm][128],f[maxm]; vector
             
               id[maxm]; int rt,L; int newnode() { memset(ch[L],-1,sizeof(ch[L])); id[L].clear(); return L++; } void init() { for(int i=0;i

q; f[rt]=rt; for(int c=0;c<128;c++){ if(ch[rt][c]==-1) ch[rt][c]=rt; else{ f[ch[rt][c]]=rt; q.push(ch[rt][c]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int c=0;c<128;c++){ if(ch[u][c]==-1) ch[u][c]=ch[f[u]][c]; else{ f[ch[u][c]]=ch[f[u]][c]; q.push(ch[u][c]); } } } } void find(char *s) { int len=strlen(s),u=rt; for(int i=0;i

>n){ ac.init(); for(int i=1;i<=n;i++){ scanf("%s",t[i]); ac.insert(t[i],i); } ac.build(); memset(cnt,0,sizeof(cnt)); scanf("%s",s); ac.find(s); for(int i=1;i<=n;i++){ if(cnt[i]){ printf("%s: %d\n",t[i],cnt[i]); } } } return 0;}

View Code