第二道AC自动机的题目了，之前参考的是网上一个博客算法，不怎么好，难写而且占空间
后来参照大白书做的这题，代码简洁多了
#include <iostream> #include <cstdio> #include <cstring> #include <map> #include <string> #include <queue> #define N 12000 using namespace std; map<string,int> mc; //防止模板里出现重复的 struct AutoTrie { int ch[N][28]; int val[N]; int f[N]; int cnt[N]; int last[N]; int sz; void init() { memset(ch[0],0,sizeof ch[0]); memset(cnt,0,sizeof cnt); //memset(val,0,sizeof val); //memset(f,0,sizeof f); mc.clear(); sz=1; } int idx(char c) { return c-'a'; } void insert(char* s,int v) { int u=0; int n=strlen(s); for (int i=0; i<n; i++) { int c=idx(s[i]); if (!ch[u][c]) { memset(ch[sz],0,sizeof ch[sz]); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; mc[string(s)]=v; } void print(int j) { if (j) { cnt[val[j]]++; print(last[j]); } } void find(char *T) { int j=0; int n=strlen(T); for (int i=0; i<n; i++) { int c=idx(T[i]); while (j && !ch[j][c]) j=f[j]; j=ch[j][c]; if (val[j]) print(j); else if (last[j]) print(last[j]); } } void build () { queue<int> q; f[0]=0; for (int c=0; c<26; c++) { int u=ch[0][c]; if (u) { f[u]=0; last[u]=0; q.push(u); } } while (!q.empty()) { int r=q.front(); q.pop(); for (int c=0; c<26; c++) { int u=ch[r][c]; if (!u) continue; q.push(u); int v=f[r]; while (v && !ch[v][c]) v=f[v]; f[u]=ch[v][c]; last[u]=val[f[u]]?f[u]:last[f[u]]; } } } }; AutoTrie ac; char cc[160][80]; char T[1000010]; int main() { int n; while (scanf("%d",&n)) { if (!n) break; ac.init(); for (int i=1; i<=n; i++) { scanf("%s",cc[i]); ac.insert(cc[i],i); } ac.build(); scanf("%s",T); ac.find(T); int sum=-1; for (int i=1; i<=n; i++) { if (ac.cnt[i]>sum) sum=ac.cnt[i]; // cout<<i<<" "<<ac.cnt[i]<<endl; } printf("%d ",sum); for (int i=1; i<=n; i++) { if (ac.cnt[mc[string(cc[i])]]==sum) { printf("%s ",cc[i]); } } } return 0; }