@Junlier
2018-08-19T22:34:56.000000Z
字数 2008
阅读 1891
字符串算法——AC自动机
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 155
#define M 10550
using namespace std;
const int Inf=1e9;
int n,tot,cnt;
struct STRING{
char s[75];
int sum,num;
}S[N];
struct EDGE{
int to,nxt;
}ljl[M];
int hd[M];
char T[1000050];
int End[N],sum[M];
int trie[M][26],fail[M];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void init()
{
tot=0,cnt=0;
memset(hd,0,sizeof(hd));
memset(sum,0,sizeof(sum));
memset(fail,0,sizeof(fail));
memset(trie,0,sizeof(trie));
}
il void AC_Insert(rg char s[],rg int num)
{
rg int now=0,L=strlen(s);
for(rg int i=0;i<L;++i)
{
rg int kk=s[i]-'a';
if(!trie[now][kk])trie[now][kk]=++tot;
now=trie[now][kk];
}
End[num]=now;
}
il void AC_get_fail()
{
queue<int>Q;
while(!Q.empty())Q.pop();
for(rg int i=0;i<26;++i)
if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty())
{
rg int now=Q.front();Q.pop();
for(rg int i=0;i<26;++i)
if(trie[now][i])
{
fail[trie[now][i]]=trie[fail[now]][i];
Q.push(trie[now][i]);
}
else trie[now][i]=trie[fail[now]][i];
}
}
il void AC_Query()
{
rg int now=0,L=strlen(T);
for(rg int i=0;i<L;++i)
{
rg int kk=T[i]-'a';
now=trie[now][kk],sum[now]++;
}
}
il void add(rg int p,rg int q){ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;}
il int cmp(rg const STRING &a,rg const STRING &b)
{
if(a.sum==b.sum)return a.num<b.num;
return a.sum>b.sum;
}
void dfs(rg int now)
{
for(rg int i=hd[now];i;i=ljl[i].nxt)
dfs(ljl[i].to),sum[now]+=sum[ljl[i].to];
}
il void AC_get_ans()
{
for(rg int i=1;i<=tot;++i)
add(fail[i],i);
dfs(0);
for(rg int i=1;i<=n;++i)
S[i].sum=sum[End[i]];
sort(S+1,S+n+1,cmp);
printf("%d\n",S[1].sum);
for(rg int i=1;i<=n;++i)
{
if(S[i].sum!=S[1].sum)break;
cout<<S[i].s<<endl;
}
}
int main()
{
while((n=read())&&n)
{
init();
for(rg int i=1;i<=n;++i)
{
scanf("%s",S[i].s);
AC_Insert(S[i].s,S[i].num=i);
}
scanf("%s",T);
AC_get_fail();
AC_Query();
AC_get_ans();
}
return 0;
}