AC自动机专题-白红宇

AC自动机专题

阅读量：5040 次

发布时间：2019-06-12

本文共 4195 字，大约阅读时间需要 13 分钟。

1 // 求目标串中出现了几个模式串  2 //====================  3 #include 
     
        4 #include 
      
         5 #include 
       
          6 #include 
        
           7 #include 
         
            8 using namespace std;  9  10 struct Trie 11 { 12     int next[500010][26],fail[500010],end[500010]; 13     int root,L; 14     int newnode() 15     { 16         for(int i = 0;i < 26;i++) 17             next[L][i] = -1; 18         end[L++] = 0; 19         return L-1; 20     } 21     void init() 22     { 23         L = 0; 24         root = newnode(); 25     } 26     void insert(char buf[]) 27     { 28         int len = strlen(buf); 29         int now = root; 30         for(int i = 0;i < len;i++) 31         { 32             if(next[now][buf[i]-'a'] == -1) 33                 next[now][buf[i]-'a'] = newnode(); 34             now = next[now][buf[i]-'a']; 35         } 36         end[now]++; 37     } 38     void build() 39     { 40         queue
          
           Q; 41 fail[root] = root; 42 for(int i = 0;i < 26;i++) 43 if(next[root][i] == -1) 44 next[root][i] = root; 45 else 46 { 47 fail[next[root][i]] = root; 48 Q.push(next[root][i]); 49 } 50 while( !Q.empty() ) 51 { 52 int now = Q.front(); 53 Q.pop(); 54 for(int i = 0;i < 26;i++) 55 if(next[now][i] == -1) 56 next[now][i] = next[fail[now]][i]; 57 else 58 { 59 fail[next[now][i]]=next[fail[now]][i]; 60 Q.push(next[now][i]); 61 } 62 } 63 } 64 int query(char buf[]) 65 { 66 int len = strlen(buf); 67 int now = root; 68 int res = 0; 69 for(int i = 0;i < len;i++) 70 { 71 now = next[now][buf[i]-'a']; 72 int temp = now; 73 while( temp != root ) 74 { 75 res += end[temp]; 76 end[temp] = 0; 77 temp = fail[temp]; 78 } 79 } 80 return res; 81 } 82 void debug() 83 { 84 for(int i = 0;i < L;i++) 85 { 86 printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]); 87 for(int j = 0;j < 26;j++) 88 printf("%2d",next[i][j]); 89 printf("]\n"); 90 } 91 } 92 }; 93 char buf[1000010]; 94 Trie ac; 95 int main() 96 { 97 int T; 98 int n; 99 scanf("%d",&T);100 while( T-- )101 {102 scanf("%d",&n);103 ac.init();104 for(int i = 0;i < n;i++)105 {106 scanf("%s",buf);107 ac.insert(buf);108 }109 ac.build();110 scanf("%s",buf);111 printf("%d\n",ac.query(buf));112 }113 return 0;114 }

//输出每个模式串出现的次数#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;char str[1010][100];struct Trie{    int next[1010*50][128],fail[1010*50],end[1010*50];    int root,L;    int newnode()    {        for(int i = 0;i < 128;i++)            next[L][i] = -1;        end[L++] = -1;        return L-1;    }    void init()    {        L = 0;        root = newnode();    }    void insert(char s[],int id)    {        int len = strlen(s);        int now = root;        for(int i = 0;i < len;i++)        {            if(next[now][s[i]] == -1)                next[now][s[i]] = newnode();            now = next[now][s[i]];        }        end[now] = id;    }    void build()    {        queue
          
           Q; fail[root] = root; for(int i = 0;i < 128;i++) if(next[root][i] == -1) next[root][i] = root; else { fail[next[root][i]] = root; Q.push(next[root][i]); } while(!Q.empty()) { int now = Q.front(); Q.pop(); for(int i = 0;i < 128;i++) if(next[now][i] == -1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int num[1010]; void query(char buf[],int n) { for(int i = 0;i < n;i++) num[i] = 0; int len=strlen(buf); int now=root; for(int i=0;i
           
            < n;i++) if(num[i] > 0) printf("%s: %d\n",str[i],num[i]); }};char buf[2000010];Trie ac;void debug(){ for (int i = 0; i < ac.L; i++) { printf("id = %3d ,fail = %3d ,end = %3d, chi = [",i,ac.fail[i],ac.end[i]); for (int j = 0; j < 128; j++) printf("%2d ",ac.next[i][j]); printf("]\n"); }}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); int n; while(scanf("%d",&n) == 1) { ac.init(); for(int i = 0;i < n;i++) { scanf("%s",str[i]); ac.insert(str[i],i); } ac.build(); scanf("%s",buf); ac.query(buf,n); } return 0;}