<span>洛谷P3796</span>
题意：有n个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。哪些模式串在文本串T中出现的次数最多。
题解：ac自动机模板加强版，开一个数组单独记录各个字符串出现的次数，找出最多的即可。（数组一定要初始化！！不然会mle！血的教训，找了半天原因，结果是初始化放进函数忘记调用了_''）
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=3e5+10; 5 string s[maxn]; 6 int num[maxn],ch[maxn][26],fail[maxn],ans[maxn]; 7 int sum,n,tot; 8 9 void init() 10 { 11 memset(num,0,sizeof(num)); 12 memset(ch,0,sizeof(ch)); 13 memset(fail,0,sizeof(fail)); 14 memset(ans,0,sizeof(ans)); 15 tot=0; 16 } 17 18 void insert(string a,int v){ 19 int now=0; 20 for(int i=0;i<a.size();i++){ 21 int x=a[i]-'a'; 22 if(!ch[now][x]) ch[now][x]=++tot; 23 now=ch[now][x]; 24 } 25 num[now]=v; 26 } 27 28 void getfail(){ 29 queue<int>q; 30 for(int i=0;i<26;i++){ 31 if(ch[0][i]){ 32 q.push(ch[0][i]); 33 fail[ch[0][i]]=0; 34 } 35 } 36 while(!q.empty()){ 37 int u=q.front();q.pop(); 38 for(int i=0;i<26;i++){ 39 int v=ch[u][i]; 40 if(!v) ch[u][i]=ch[fail[u]][i]; 41 else { 42 fail[v]=ch[fail[u]][i]; 43 q.push(v); 44 } 45 } 46 } 47 } 48 49 void query(string a){ 50 int now=0; 51 for(int i=0;i<a.size();i++){ 52 int p=a[i]-'a'; 53 now=ch[now][p]; 54 for(int j=now;j;j=fail[j]) 55 ans[num[j]]++; 56 } 57 } 58 59 int main() 60 { 61 while(cin>>n&&n){ 62 init(); //一定初始化！！ 63 for(int i=1;i<=n;i++){ 64 cin>>s[i]; 65 insert(s[i],i); 66 } 67 getfail(); 68 string k; 69 cin>>k; 70 query(k); 71 sum=0; 72 for(int i=1;i<=n;i++) 73 if(ans[i]>sum) sum=ans[i]; 74 cout<<sum<<endl; 75 for(int i=1;i<=n;i++) 76 if(ans[i]==sum) cout<<s[i]<<endl; 77 } 78 return 0; 79 }
