题解 P3796 【【模板】AC自动机（加强版）】

zhuixun_ · 2019-06-17 20:26:38 · 题解

不会AC自动机，但不妨碍做本题，

水题,trie树暴力匹配过~

注意输出结果时要按照输入的顺序排序。

#include<bits/stdc++.h>
using namespace std;
int n;
int tot=0;
const int N=150*70+10;
int ch[N][26],vis[N],mark[(int)(1e6+10)];

struct node{
    string str;
    int num;//统计每个模板串出现次数
    int appear;//记录每个模板串出现的时间
    bool operator <(const node &b){
        if(num==b.num) return appear<b.appear;
        return num>b.num;
    }

    void init(){
        num=0;
        str="";
    }
}mp[N];

void add(string str,int appear){
    int u=0;
    for(int i=0;i<str.size();i++){
        int id=str[i]-'a';
        if(!ch[u][id]) ch[u][id]=++tot;
        u=ch[u][id];
    }
    vis[u]=1;
    mp[u].str=str;
    mp[u].appear=appear;
}

void check(string str){
    for(int k=0;k<str.size();k++){
        int u=0;
        for(int i=k;i<str.size();i++){
            int id=str[i]-'a';
            if(ch[u][id]) u=ch[u][id];
            else break;

            if(vis[u]) mp[u].num++;
        }
    }
}
int main(){
    freopen("p.txt","r",stdin);
    while(scanf("%d",&n)&&n){
        memset(vis,0,sizeof(vis));
        memset(ch,0,sizeof(ch));
        for(int i=0;i<N;i++) mp[i].init();
        tot=0;

        for(int i=0;i<n;i++){
            string str;
            cin>>str;
            add(str,i);
        }

        string T;
        cin>>T;
        check(T);

        sort(mp,mp+N);
        int pos=mp[0].num;
        printf("%d\n",pos);
        for(int i=0;i<N;i++){
            if(mp[i].num==pos) cout<<mp[i].str<<"\n";
            else break;
        }
    }
    return 0;
}