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

· · 题解

貌似跑得还不是很慢？

不过一开始没按输入顺序输入一片wa。。。/(ㄒoㄒ)/~~

其实乍一看还挺难的，

然而想一下发现并不难

建议先做简单版再来

这里相对简单版只要改几个地方就可以了

首先我们增加一个father数组记录father，一个a数组记录每个节点存的是哪个字符，以便输出

然后将ans变为一个结构体

num的作用是判断顺序以及记录节点位置

在匹配文本串的时候，每匹配到一个，就把对应节点的ans.date++，

同时注意val不能清零，因为要支持一个串多次出现。

由于我们是按顺序插入模式串，所以每个模式串的结尾对应的节点的下标是单调上升的，因此num小即代表输入顺序靠前 因此在最后统计答案的时候按照date为第一关键字，num为第二关键字排序，并输出即可

由于ans是直接统计在结尾节点对应下标上的， 所以直接就得到了对应串的结尾位置在哪， 然后增加一个数组，（为了实现正序输出） 因为从下面跑到上面的话，访问的次序其实是倒的，如果直接输出就会把模式串倒过来，因此开一个数组记录即可。 注意每次都要初始化

#include<bits/stdc++.h>
using namespace std;
#define maxn 10510
#define R register int
int n;char s[1000005];
int q[1000005],head,tail;
int father[maxn],a[maxn];
int c[maxn][26],val[maxn],fail[maxn],tot;
char out[80];

struct abc{
    int date,num;
}ans[maxn];

struct Aho_Corasick_Automaton
{
    void add()//加入trie树
    {
        int len=strlen(s),now=0;
        for(R i=0;i<len;i++)
        {
            int v=s[i]-'a';//记录是哪个个字母
            if(!c[now][v])  c[now][v]=++tot,father[tot]=now,a[tot]=v;
            now=c[now][v];
        }
        val[now]++;
    }

    void build()
    {
        R now;
        head=tail=0;
        for(R i=0;i<26;i++)
            if(c[0][i]) fail[c[0][i]]=0,q[++tail]=c[0][i];
        while(head<tail)
        {
            now=q[++head];
            for(R i=0;i<26;i++)
                if(c[now][i]) fail[c[now][i]]=c[fail[now]][i],q[++tail]=c[now][i];
                else c[now][i]=c[fail[now]][i];//如果father的最长公共前缀的下一个刚好可以匹配的话，就直接把fail指过去就可以了
        }
    }

    void search()
    {
        int len=strlen(s),now=0;
        for(R i=0;i<len;i++)
        {
            now=c[now][s[i]-'a'];
            for(R t=now; t && ~val[t] ;t=fail[t]) ans[t].date+=val[t];
        }
    }
}AC;

bool cmp(abc a,abc b)
{
    if(a.date!=b.date) return a.date>b.date;
    if(a.num!=b.num) return a.num<b.num;//error!!!因为输出要按输入顺序
}

void work()
{
    R now,cnt=0;

    while(1)
    {
        scanf("%d",&n);
        if(!n)return ;
        tot=0;
        memset(c,0,sizeof(c));
        for(R i=1;i<=maxn;i++)ans[i].date=0;
        memset(val,0,sizeof(val));
        for(R i=1;i<=maxn;i++)  ans[i].num=i;//由于每次sort后都会打乱num的次序，所以与其再sort一次，不如扫一遍重新赋值

        for(R i=1;i<=n;i++) scanf("%s",s),AC.add();
        AC.build();
        scanf("%s",s);
        AC.search();
        sort(ans+1,ans+maxn,cmp);
        printf("%d\n",ans[1].date);
        now=ans[1].num;
        cnt=0;
        while(now)
        {
            out[++cnt]=a[now]+'a';
            now=father[now];
        }
        for(R i=cnt;i>=1;i--) printf("%c",out[i]);
        printf("\n");
        for(R i=2;i<=n;i++)
        {
            if(ans[i].date!=ans[i-1].date)  break;
            now=ans[i].num;
            cnt=0;
            while(now)
            {
                out[++cnt]=a[now]+'a';
                now=father[now];
            }
            for(R i=cnt;i>=1;i--) printf("%c",out[i]);
            printf("\n");
        }
    }
}

int main()
{
    freopen("in.in","r",stdin);
    work();
    fclose(stdin);
    return 0;
}