AC 自动机输出出现次数最多的模式串

た入场券 2024-04-17 18:32 42阅读 0赞

有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出**哪些**模式串在文本串TT中出现的次数最多。

### 输入格式 ###

输入含多组数据。

每组数据的第一行为一个正整数NN，表示共有NN个模式串，1 \\leq N \\leq 1501≤N≤150。

接下去NN行，每行一个长度小于等于7070的模式串。下一行是一个长度小于等于10^6106的文本串TT。

输入结束标志为N=0N=0。

### 输出格式 ###

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

### 输入输出样例 ###

**输入 \#1**复制

2
    aba
    bab
    ababababac
    6
    beta
    alpha
    haha
    delta
    dede
    tata
    dedeltalphahahahototatalpha
    0

**输出 \#1**复制

4
    aba
    2
    alpha
    haha

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e6+50;
    char d[150][100],a[M];
    int ans[200],n;
    struct AC_AUTO{
        int ch[13000][26],fail[13000],cnt,val[13000];
        void reset(){
            cnt=0;
            memset(ch,0,sizeof(ch));
            memset(fail,0,sizeof(fail));
            memset(ans,0,sizeof(ans));
            memset(val,0,sizeof(val));
        }
        void ins(char *s,int id){
            int now=0,len=strlen(s);
            for(int v,i=0;i<len;i++){
                v=s[i]-'a';
                if(!ch[now][v])ch[now][v]=++cnt;
                now=ch[now][v];
            }
            val[now]=id;
        }
        void getfail(){
            queue<int>q;
            for(int i=0;i<26;i++)
                if(ch[0][i])
                    fail[ch[0][i]]=0,q.push(ch[0][i]);
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int i=0;i<26;i++)
                    if(ch[u][i])fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
                    else ch[u][i]=ch[fail[u]][i];
            }
        }
        void query(char *s){
            int len=strlen(s);
            int now=0;
            for(int i=0;i<len;i++){
                now = ch[now][s[i]-'a'];
                for(int t=now;t;t=fail[t])
                    ans[val[t]]+=1;
            }
        }
    }AC;
    int main(){
        while(scanf("%d",&n)!=EOF&&n){
            AC.reset();
            for(int i=1;i<=n;i++){
                scanf("%s",d[i]);
                AC.ins(d[i],i);
            }
            AC.getfail();
            scanf("%s",a);
            AC.query(a);
            for(int i=ans[0]=0;i<=n;i++)if(ans[0]<ans[i])ans[0]=ans[i];
            printf("%d\n",ans[0]);
            for(int i=1;i<=n;i++)if(ans[i]==ans[0])printf("%s\n",d[i]);
        }
    
        return 0;
    }