UVA 1449 Dominating Patterns(AC自动机)
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36265
题意：
给你n个单词，还有一个长文本s，现在要你输出在文本s中出现次数最多的单词。
分析：
直接建立AC自动机，并且val值是当前插入单词的编号。建立AC自动机后，用s文本串去匹配，每当走过val非0的节点后都使得对应单词的cnt值+1.最后一遍扫描cnt数组，然后求出max值。然后在扫描一遍输入单词，只要当前单词的cnt值==max就输出当前单词。
注意：这里有个问题。如果输入单词有重复的情况如：
单词aaa输入了两遍的话，那么在建立Trie的时候后来的aaa覆盖了前一个aaa，最终算得cnt[i]=0，cnt[i+1]=5。结果我们就只输出了一个aaa。其实我们应该输出两次aaa（在最终结果里）。这里我们应该做个map映射，将字符串=="aaa"的所有单词始终映射到序号x上，最终cnt[x]的值=5=max，最后我们扫描一遍单词aaa，用过map[aaa]来获得aaa的序号为x,这样就可以输出2遍aaa了。
AC代码：
#include<cstdio> #include<queue> #include<cstring> #include<map> #include<string> #include<iostream> using namespace std; const int maxnode=11000; const int sigma_size=26; map<string,int >ms; struct AC_Automata { int ch[maxnode][sigma_size]; int val[maxnode]; int f[maxnode]; int last[maxnode]; int sz; int cnt[200];//计算字符串出现的次数 void init() { sz=1; memset(ch[0],0,sizeof ch[0]); memset(cnt,0,sizeof cnt); ms.clear(); } void insert(char *s,int v)//v是单词s输入的序号 { int n=strlen(s),u=0; for(int i=0;i<n;i++) { int id=s[i]-'a'; if(ch[u][id]==0) { ch[u][id]=sz; memset(ch[sz],0,sizeof ch[sz]); val[sz++]=0; } u=ch[u][id]; } val[u]=v; ms[string(s)]=v; } void print(int i) { if(val[i]) { cnt[val[i]]++; print(last[i]); } } void find(char *s) { int n=strlen(s); int j=0; for(int i=0;i<n;i++) { int id=s[i]-'a'; while(j&&ch[j][id]==0)j=f[j]; j=ch[j][id]; if(val[j])print(j); else if(val[last[j]]) print(last[j]); } } void getfail() { queue<int >q; last[0]=f[0]=0; for(int i=0;i<sigma_size;i++) { int u=ch[0][i]; if(u) { f[u]=last[u]=0; q.push(u); } } while(!q.empty()) { int r=q.front(); q.pop(); for(int i=0;i<sigma_size;i++) { int u=ch[r][i]; if(!u)continue; q.push(u); int v=f[r]; while(v&&ch[v][i]==0)v=f[v]; f[u]=ch[v][i]; last[u]=val[f[u]]?f[u]:last[f[u]]; } } } }ac; char word[160][80]; char text[1000000+1000]; int main() { int n; while(~scanf("%d",&n)&&n) { ac.init(); for(int i=1;i<=n;i++) { scanf("%s",word[i]); ac.insert(word[i],i); } //cout<<"+++"<<endl; ac.getfail(); scanf("%s",text); ac.find(text); int maxe=-1; for(int i=1;i<=n;i++) { if(ac.cnt[i]>maxe) maxe=ac.cnt[i]; } printf("%d\n",maxe); for(int i=1;i<=n;i++) { if(ac.cnt[ms[string(word[i])]]==maxe) printf("%s\n",word[i]); } } }
