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

· · 题解

一道模板题，然而我搞了1小时，可能是我还是太菜了~~

如果你还不知道AC自动机是什么那就[]()

这个比简单版稍微有所改动，那么这里我们就用一个ans数组存一下答案 因为我们要求解出现的次数，于是就不用标记了，在失配时只需要判断j是否为 0就可以了，如果是一个单词的末尾（也就是cnt>0）就用ans记一下就OK了。

其他的话基本一样，不过还有一点！就是排序时要按输入顺序来，不然只有20分， 我就是在这卡了好久。```

Code


#include<bits/stdc++.h>
#define N 160
using namespace std;
struct node{
    int fail,cnt;
    int next[26];
}AC[N*100];
struct no{
    int id,num;
}ans[N*100];
int n,k=0,tot=0;
char a[N][N],text[N*N*N];
void build(int id,char *s,int now){
    int len=strlen(s);
    for(int i=0;i<len;i++){
        int j=s[i]-'a';
        if(AC[id].next[j]==0) AC[id].next[j]=++k;
        id=AC[id].next[j];
    }
    AC[id].cnt=now;ans[now].id=now;
}
void match(int id){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(AC[id].next[i]==0) continue;
        AC[AC[id].next[i]].fail=id;
        q.push(AC[id].next[i]);
    }
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(AC[now].next[i]==0){
                AC[now].next[i]=AC[AC[now].fail].next[i];
                continue;
            }
            AC[AC[now].next[i]].fail=AC[AC[now].fail].next[i];
            q.push(AC[now].next[i]);
        }
    }
}
void sovel(int id,char *s){
    int len=strlen(s);
    for(int i=0;i<len;i++){
        int j=AC[id].next[s[i]-'a'];
        while(j!=0){
            if(AC[j].cnt>0) ans[AC[j].cnt].num++;
            j=AC[j].fail;
        }
        id=AC[id].next[s[i]-'a'];
    }
}
bool cmp(no a,no b){
    if(a.num==b.num) return a.id<b.id;
    return a.num>b.num;
}
int main()
{
    while(1){
        k=0;tot=0;
        memset(&AC,0,sizeof(AC));memset(&ans,0,sizeof(ans));
        scanf("%d",&n);
        if(n==0) break;
        for(int i=1;i<=n;i++) {scanf(" %s",a[i]),build(0,a[i],i);}
        match(0);
        scanf(" %s",text);
        sovel(0,text);
        sort(ans+1,ans+n+1,cmp);
        printf("%d\n%s\n",ans[1].num,a[ans[1].id]);
        for(int i=2;i<=n;i++){
            if(ans[i].num!=ans[i-1].num) break;
            printf("%s\n",a[ans[i].id]);
        }
    }
    return 0;
}