uva-1449-AC自动机

题目大意:给出N(N<150)个长度不超过L(70)的匹配串和一个长度小于1e6的文本串，在文本串中找出出现次数最多的匹配串，如果有多个匹配串满足条件，按输入顺序依次输出。

AC自动机复杂度约为O((N+M)*L) //N为匹配串个数，M为文本串长度，L为匹配串平均长度，时间3s，可行

用了两个map方便统计字符串出现的次数和根据节点编号找到对应的字符串，注意这里统计时不必将AC[u].cnt清零;

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int MAX_T=1000006;
  4 const int MAX_NOD=150*70+15;
  5 const int MAX_SIG=26;
  6 const int MAX_P=71;
  7 map<string,int> M;
  8 map<int,string> _M;
  9 char T[MAX_T];
 10 struct node{
 11     int next[MAX_SIG];
 12     int fail,cnt;
 13 };
 14 struct aho
 15 {
 16     node AC[MAX_NOD];
 17     int size;
 18 
 19     int idx(char c){return c-'a';}
 20 
 21     void init()
 22     {
 23         for(int i=0;i<MAX_NOD;++i)
 24             memset(AC[i].next,0,sizeof(AC[i].next)),AC[i].cnt=0;
 25         size=1;
 26         AC[0].fail=-1;
 27     }
 28 
 29     void insert(char *S)
 30     {
 31         int n=strlen(S);
 32         int u=0;
 33         for(int i=0;i<n;++i)
 34         {
 35             int c=idx(S[i]);
 36             if(!AC[u].next[c]) AC[u].next[c]=size++;
 37             u=AC[u].next[c];
 38         }
 39         AC[u].cnt++;
 40         _M[u]=S;
 41         //cout<<"---"<<_M[u]<<" "<<AC[u].cnt<<endl;
 42     }
 43 
 44     void build_fail()
 45     {
 46         queue<int> q;
 47         q.push(0);
 48         AC[0].fail=-1;
 49         while(!q.empty()){
 50             int u=q.front();
 51             q.pop();
 52             for(int i=0;i<MAX_SIG;++i)
 53             {
 54                 if(AC[u].next[i]){
 55                     if(!u) AC[AC[u].next[i]].fail=0;
 56                     else{
 57                         int v=AC[u].fail;
 58                         while(v!=-1&&AC[v].next[i]==0) v=AC[v].fail;
 59                         if(v==-1) AC[AC[u].next[i]].fail=0;
 60                         else AC[AC[u].next[i]].fail=AC[v].next[i];
 61                     }
 62                     q.push(AC[u].next[i]);
 63                 }
 64             }
 65         }
 66     }
 67 
 68     void cal(int u)
 69     {
 70         while(u!=-1){//cout<<"ppp"<<endl;
 71             M[_M[u]]+=AC[u].cnt;
 72           //  AC[u].cnt=0;
 73             u=AC[u].fail;
 74         }
 75     }
 76 
 77     int solve(char *T)
 78     {
 79         int now=0;
 80         int n=strlen(T);
 81         for(int i=0;i<n;++i)
 82         {
 83             int c=idx(T[i]);
 84             if(AC[now].next[c]) now=AC[now].next[c];
 85             else{
 86                 int v=AC[now].fail;
 87                 while(v!=-1&&AC[v].next[c]==0) v=AC[v].fail;
 88                 if(v==-1){now=0;}
 89                 else{
 90                     now=AC[v].next[c];
 91                 }
 92             }
 93             if(AC[now].cnt){
 94                 cal(now);
 95             }
 96         }
 97     }
 98 };
 99 int main()
100 {
101     int n;
102     char P[MAX_P];
103     string x[155];
104     while(cin>>n&&n){
105         M.clear();
106         _M.clear();
107         aho a;
108         a.init();
109         for(int i=1;i<=n;++i)
110         {
111             cin>>P;
112             x[i]=P;
113             M[P]=0;
114             a.insert(P);
115         }
116         cin>>T;
117         a.build_fail();
118         int ans=0;
119         a.solve(T);
120         for(int i=1;i<=n;++i)
121             ans=max(ans,M[x[i]]);
122         cout<<ans<<endl;
123         for(int i=1;i<=n;++i)
124         {
125             if(M[x[i]]==ans) cout<<x[i]<<endl;
126         }
127     }
128     return 0;
129 }
130 /*
131 2
132 aba
133 bab
134 ababababac
135 6
136 beta
137 alpha
138 haha
139 delta
140 dede
141 tata
142 dedeltalphahahahototatalpha
143 0
144 */