HDU 3065 病毒侵袭持续中（AC自动机）

　　这题数据太水，一开始没有加上Get的方法也能AC。。话说AC自动机中一定要注意加上Get的方法！（不然，同一个后缀的其他单词就没被算上了。）

　　代码如下：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <queue>
  5 #include <string>
  6 #include <map>
  7 #include <iostream>
  8 using namespace std;
  9 const int MAX_N = 2000000 + 50;
 10 const int MAX_Tot = 1000*50 + 50;
 11 
 12 int ans[1000+5];
 13 map<int,string> M;
 14 
 15 struct Aho
 16 {
 17     struct state
 18     {
 19         int nxt[26];
 20         int fail,cnt;
 21     }stateTable[MAX_Tot];
 22 
 23     int size;
 24 
 25     queue<int> que;
 26 
 27     void init()
 28     {
 29         while(que.size()) que.pop();
 30         for(int i=0;i<MAX_Tot;i++)
 31         {
 32             memset(stateTable[i].nxt,0,sizeof(stateTable[i].nxt));
 33             stateTable[i].fail = stateTable[i].cnt = 0;
 34         }
 35         size = 1;
 36     }
 37 
 38     void insert(char *s,int which)
 39     {
 40         int n = strlen(s);
 41         int now = 0;
 42         for(int i=0;i<n;i++)
 43         {
 44             char c = s[i];
 45             if(!stateTable[now].nxt[c-'A'])
 46                 stateTable[now].nxt[c-'A'] = size++;
 47             now = stateTable[now].nxt[c-'A'];
 48         }
 49         stateTable[now].cnt = which;
 50     }
 51 
 52     void build()
 53     {
 54         stateTable[0].fail = -1;
 55         que.push(0);
 56 
 57         while(que.size())
 58         {
 59             int u = que.front();que.pop();
 60             for(int i=0;i<26;i++)
 61             {
 62                 if(stateTable[u].nxt[i])
 63                 {
 64                     if(u == 0) stateTable[stateTable[u].nxt[i]].fail = 0;
 65                     else
 66                     {
 67                         int v = stateTable[u].fail;
 68                         while(v != -1)
 69                         {
 70                             if(stateTable[v].nxt[i])
 71                             {
 72                                 stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
 73                                 break;
 74                             }
 75                             v = stateTable[v].fail;
 76                         }
 77                         if(v == -1) stateTable[stateTable[u].nxt[i]].fail = 0;
 78                     }
 79                     que.push(stateTable[u].nxt[i]);
 80                 }
 81             }
 82         }
 83     }
 84     
 85     void Get(int u)
 86     {
 87         while(u)
 88         {
 89             ans[stateTable[u].cnt] ++;
 90             u = stateTable[u].fail;
 91         }
 92     }
 93 
 94     void match(char *s)
 95     {
 96         int n = strlen(s);
 97         int now = 0;
 98         for(int i=0;i<n;i++)
 99         {
100             char c = s[i];
101             if(c<'A' || c>'Z') {now = 0;continue;}
102             if(stateTable[now].nxt[c-'A']) now = stateTable[now].nxt[c-'A'];
103             else
104             {
105                 int p = stateTable[now].fail;
106                 while(p != -1 && stateTable[p].nxt[c-'A'] == 0) p = stateTable[p].fail;
107                 if(p == -1) now = 0;
108                 else now = stateTable[p].nxt[c-'A'];
109             }
110             if(stateTable[now].cnt)
111             {
112                 Get(now);
113                 //ans[stateTable[now].cnt] ++;
114                 /*
115                     一定要用Get这样的方法，
116                     不然，同一个后缀的无法被算上了
117                 */
118             }
119         }
120     }
121 }aho;
122 
123 int n;
124 char s[MAX_N];
125 
126 int main()
127 {
128     while(scanf("%d",&n)==1)
129     {
130         memset(ans,0,sizeof(ans));
131         M.clear();
132         aho.init();
133         for(int i=1;i<=n;i++)
134         {
135             scanf("%s",s);
136             M[i] = s;
137             aho.insert(s,i);
138         }
139         aho.build();
140         scanf("%s",s);
141         aho.match(s);
142         for(int i=1;i<=n;i++)
143         {
144             if(ans[i])
145             {
146                 cout << M[i] << ": " << ans[i] << endl;
147             }
148         }
149     }
150 }

————————————————————————————————————————————

　　发现上面的代码有问题（虽然能AC），正确代码如下：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <queue>
  5 #include <string>
  6 #include <map>
  7 #include <iostream>
  8 using namespace std;
  9 const int MAX_N = 2000000 + 50;
 10 const int MAX_Tot = 1000*50 + 50;
 11 
 12 int ans[1000+5];
 13 map<int,string> M;
 14 
 15 struct Aho
 16 {
 17     struct state
 18     {
 19         int nxt[26];
 20         int fail,cnt;
 21     }stateTable[MAX_Tot];
 22 
 23     int size;
 24 
 25     queue<int> que;
 26 
 27     void init()
 28     {
 29         while(que.size()) que.pop();
 30         for(int i=0;i<MAX_Tot;i++)
 31         {
 32             memset(stateTable[i].nxt,0,sizeof(stateTable[i].nxt));
 33             stateTable[i].fail = stateTable[i].cnt = 0;
 34         }
 35         size = 1;
 36     }
 37 
 38     void insert(char *s,int which)
 39     {
 40         int n = strlen(s);
 41         int now = 0;
 42         for(int i=0;i<n;i++)
 43         {
 44             char c = s[i];
 45             if(!stateTable[now].nxt[c-'A'])
 46                 stateTable[now].nxt[c-'A'] = size++;
 47             now = stateTable[now].nxt[c-'A'];
 48         }
 49         stateTable[now].cnt = which;
 50     }
 51 
 52     void build()
 53     {
 54         stateTable[0].fail = -1;
 55         que.push(0);
 56 
 57         while(que.size())
 58         {
 59             int u = que.front();que.pop();
 60             for(int i=0;i<26;i++)
 61             {
 62                 if(stateTable[u].nxt[i])
 63                 {
 64                     if(u == 0) stateTable[stateTable[u].nxt[i]].fail = 0;
 65                     else
 66                     {
 67                         int v = stateTable[u].fail;
 68                         while(v != -1)
 69                         {
 70                             if(stateTable[v].nxt[i])
 71                             {
 72                                 stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
 73                                 break;
 74                             }
 75                             v = stateTable[v].fail;
 76                         }
 77                         if(v == -1) stateTable[stateTable[u].nxt[i]].fail = 0;
 78                     }
 79                     que.push(stateTable[u].nxt[i]);
 80                 }
 81             }
 82         }
 83     }
 84 
 85     void Get(int u)
 86     {
 87         while(u)
 88         {
 89             ans[stateTable[u].cnt] ++;
 90             u = stateTable[u].fail;
 91         }
 92     }
 93 
 94     void match(char *s)
 95     {
 96         int n = strlen(s);
 97         int now = 0;
 98         for(int i=0;i<n;i++)
 99         {
100             char c = s[i];
101             if(c<'A' || c>'Z') {now = 0;continue;}
102             if(stateTable[now].nxt[c-'A']) now = stateTable[now].nxt[c-'A'];
103             else
104             {
105                 int p = stateTable[now].fail;
106                 while(p != -1 && stateTable[p].nxt[c-'A'] == 0) p = stateTable[p].fail;
107                 if(p == -1) now = 0;
108                 else now = stateTable[p].nxt[c-'A'];
109             }
110             //if(stateTable[now].cnt)
111             {
112                 Get(now);
113             }
114         }
115     }
116 }aho;
117 
118 int n;
119 char s[MAX_N];
120 
121 int main()
122 {
123     while(scanf("%d",&n)==1)
124     {
125         memset(ans,0,sizeof(ans));
126         M.clear();
127         aho.init();
128         for(int i=1;i<=n;i++)
129         {
130             scanf("%s",s);
131             M[i] = s;
132             aho.insert(s,i);
133         }
134         aho.build();
135         scanf("%s",s);
136         aho.match(s);
137         for(int i=1;i<=n;i++)
138         {
139             if(ans[i])
140             {
141                 cout << M[i] << ": " << ans[i] << endl;
142             }
143         }
144     }
145 }
146 /*
147 3
148 ABCDEFG
149 ABCDE
150 DEF
151 ABCDEFG
152 */

View Code