LA 4670




Type:AC自动机

题意

给你一堆子串和一个主串

问你在主串中出现次数最多的子串有哪些,最后结果按字典序排列

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=11000;
const int maxm=152;
const int maxt=1e6+6;

int T,N,tot_len;
char str[maxm][80],tot[maxt];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cnt[maxn],val[maxn];
    bool vis[maxn][sigma_size];

    int siz,root,max_time;

    vector<string> ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        for(int i=0;i<sigma_size;++i){
            vis[siz][i]=false;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans.clear();
        for(int i=0;i<maxn;++i) val[i]=cnt[i]=0;
        siz=0;root=0;max_time=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];

            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                if(!vis[p][c]){
                    cnt[val[p]]++;
                    max_time=max(cnt[val[p]],max_time);
                    p=f[p];
                    vis[p][c]=true;
                }
            }
        }
    }

    void print(){
        printf("%d\n",max_time);
        for(int i=1;i<=N;++i){
            if(cnt[i]==max_time){
                ans.push_back(str[i]);
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i){
            cout<<ans[i]<<endl;
        }
    }
}aho;

int main(){
    while(~scanf("%d",&N) && N){
        aho.init();
        for(int i=1;i<=N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(tot);
        tot_len=strlen(tot);
        //cout<<tot_len<<endl;
        aho.Find(tot);
        aho.print();
    }
    return 0;
}