LA4670 Dominating Patterns[AC自动机]

本文主要是介绍LA4670 Dominating Patterns[AC自动机]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The archaeologists are going to decipher a very mysterious “language”. Now, they know many language patterns; each pattern can be treated as a string on English letters (only lower case). As a sub string,these patterns may appear more than one times in a large text string (also only lower case English letters).
What matters most is that which patterns are the dominating patterns. Dominating pattern is the pattern whose appearing times is not less than other patterns.
It is your job to find the dominating pattern(s) and their appearing times.
Input
The entire input contains multi cases. The first line of each case is an integer, which is the number of patterns N, 1 ≤ N ≤ 150. Each of the following N lines contains one pattern, whose length is in range[1, 70]. The rest of the case is one line contains a large string as the text to lookup, whose length is up to 1E6
.
At the end of the input file, number ‘0’ indicates the end of input file.
Output
For each of the input cases, output the appearing times of the dominating pattern(s). If there are more than one dominating pattern, output them in separate lines; and keep their input order to the output.
Sample Input
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
Sample Output
4
aba
2
alpha
haha

题意：对于给定的字典和句子，输出出现次数最多的单词的出现次数并且按输入顺序顺出在句子中出现次数最多的单词。
分析：就是AC加上离散一下（是离散？不清楚，汝佳用的map,某大神用的hash，我就直接存下来了每次输入的所有单词并且存下来了这个单词对应的叶子节点，到时候直接访问对比tot,两次分开的n的循环就可以了。这里的重复出现的单词我个人认为就用出现的顺序来区分很方便，因为在tot上覆盖就覆盖啊，反正最后得到的tot两个相同的单词都一样的……
第一次完全脱离模板写AC，还有一点不熟练，把有的细节忘了写了，要多熟练一下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=150*70+5;
char s[155][75],ov[1000005];
int n,ch[maxn][30],len,inde,sig[maxn],last[maxn],mapy[155],ans,tot[maxn],nxt[maxn];
int calc(char c)
{return c-'a';
}
void insert(int cur)
{len=strlen(s[cur]);int u=0;for(int i=0;i<len;i++){if(!ch[u][calc(s[cur][i])])ch[u][calc(s[cur][i])]=++inde;u=ch[u][calc(s[cur][i])];}sig[u]++;mapy[cur]=u;
}
void getfail()
{queue<int>q;nxt[0]=0;for(int i=0;i<26;i++)if(ch[0][i])//0不处理...因为好像本来跑回0也没有问题？q.push(ch[0][i]);while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++)if(ch[cur][i]){int u=ch[cur][i];q.push(u);int j=nxt[cur];while(j&&!ch[j][i])j=nxt[j];nxt[u]=ch[j][i];last[u]=sig[nxt[u]]?nxt[u]:last[nxt[u]];}else ch[cur][i]=ch[nxt[cur]][i];}
}
void init()
{clr(ch);clr(nxt);clr(last);clr(tot);inde=0;ans=0;for(int i=1;i<=n;i++){scanf("%s",s[i]);insert(i);}scanf("%s",ov);getfail();
}
void print(int j)
{if(j){tot[j]++;print(last[j]);}
}
void mat()
{int j=0;len=strlen(ov);for(int i=0;i<len;i++){j=ch[j][calc(ov[i])];if(sig[j])print(j);else print(last[j]);}for(int i=1;i<=n;i++)ans=max(ans,tot[mapy[i]]);printf("%d\n",ans);for(int i=1;i<=n;i++)if(tot[mapy[i]]==ans)printf("%s\n",s[i]);
}
int main()
{freopen("LA4670.in","r",stdin);freopen("LA4670.out","w",stdout);scanf("%d",&n);//for(scanf("%d",&n);n;scanf("%d",&n))while(n){init();mat();scanf("%d",&n);}return 0;
}