AC 自动机（C++ 实现）

admin

[mw_shl_code=c,true]#include<bits/stdc++.h>
using namespace std;
const int maxN(15e1),maxL(7e1),maxS(26);
int n;
string s[maxN+5],t;
struct AC_automaton{
        int cnt,tree[maxN*maxL+5][maxS+5],end[maxN*maxL+5],frm[maxN*maxL+5],fail[maxN*maxL+5],vistot[maxN*maxL+5],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[c])tree[c]=++cnt;u=tree[c];
                }
                ++end,frm=from;
        }
        void Get_fail(){
                queue<int>q;
                for(int i(1);i<=maxS;++i)if(tree[0])fail[tree[0]]=0,q.push(tree[0]);
                while(q.size()){
                        int u(q.front());q.pop();
                        for(int i(1);i<=maxS;++i){
                                int v(tree);
                                if(v)fail[v]=tree[fail],q.push(v);
                                else tree=tree[fail];
                        }
                }
        }
        void query(string t){
                int u(0);
                for(int i(0);i<t.size();++i){
                        u=tree[t-'a'+1];
                        for(int v(u);v;v=fail[v])if(frm[v])++vistot[frm[v]],maxvistot=max(maxvistot,vistot[frm[v]]);
                }
                printf("%d\n",maxvistot);
                for(int i(1);i<=cnt;++i)
                        if(vistot[frm]==maxvistot){
                                for(int j(0);j<s[frm].size();++j)printf("%c",s[frm][j]);
                                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;
}[/mw_shl_code]