AC 自动机（C++ 实现）
#include<bits/stdc++.h>using namespace std;
const int maxN(15e1),maxL(7e1),maxS(26);
int n;
string s,t;
struct AC_automaton{
int cnt,tree,end,frm,fail,vistot,maxvistot;
void init(){
cnt=0,memset(tree,0,sizeof(tree)),memset(end,0,sizeof(end)),
memset(frm,0,sizeof(frm)),memset(fail,0,sizeof(fail)),
memset(vistot,0,sizeof(vistot)),maxvistot=0;
}
void insert(string s,int from){
int u(0);
for(int i(0);i<s.size();++i){
int c(s-'a'+1);
if(!tree)tree=++cnt;u=tree;
}
++end,frm=from;
}
void Get_fail(){
queue<int>q;
for(int i(1);i<=maxS;++i)if(tree)fail]=0,q.push(tree);
while(q.size()){
int u(q.front());q.pop();
for(int i(1);i<=maxS;++i){
int v(tree);
if(v)fail=tree],q.push(v);
else tree=tree];
}
}
}
void query(string t){
int u(0);
for(int i(0);i<t.size();++i){
u=tree-'a'+1];
for(int v(u);v;v=fail)if(frm)++vistot],maxvistot=max(maxvistot,vistot]);
}
printf("%d\n",maxvistot);
for(int i(1);i<=cnt;++i)
if(vistot]==maxvistot){
for(int j(0);j<s].size();++j)printf("%c",s]);
puts("");
}
}
}AhoC;
int main(){
while(scanf("%d",&n)){
if(!n)break;
AhoC.init();
for(int i(1);i<=n;++i)cin>>s,AhoC.insert(s,i);
AhoC.Get_fail();
cin>>t,AhoC.query(t);
}
return 0;
}
页:
[1]