题目描述

给我们n个字典串,再给我们一个匹配串,问每一个字典串在匹配串中出现了多少次
n<=2e5, Σ|T|<=2e5.

样例

输入

5
a
bb
aa
abaa
abaaa
abaaabaa

输出

6
0
3
2
1

分析

还是把匹配串放进AC自动机中运行,每匹配到一个点,我们就把这个点的出现次数+1,同时这个点表示的前缀出现了,也说明这个点的fail链上的所有点表示的前缀出现,我们也需要把fail链上的所有点的出现次数+1.但是我们可以每匹配到一个点就去跳一边fail链吗,我们算一下复杂度,走匹配串的时间复杂度是O(|S|),每次跳fail链,最坏情况是O(|T|),故最终的时间复杂度是O(|S|*|T|),这样肯定会超时的.那我们怎么优化的,我们刚刚是说匹配到一个点需要把他的fail链上的点的答案都+1,如果我们反过来看,一个点的出现次数等于什么呢,答案是等于这个点的fail树的子树中的每个点的出现次数之和.所以我们最后把答案从下往上推即可.我们在构建AC自动机时的队列数组里面的顺序就是fail树的一个拓扑序,我们倒着遍历队列数组累加答案即可.

AC自动机

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10,M = 2e5+10;
int tr[M][26],st[M],idx;
int id[M],cnt[M];//第i个字符串的节点位置   以i为终止节点的字符串出现了多少次
int fail[M],q[M];
char s[N];
int n;
int h[M],e[M],ne[M],p;
int sum[M];
void add(int a,int b)
{
    e[p]=b,ne[p]=h[a],h[a]=p++;
}
int insert()
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'a';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    st[u]=1;
    return u;
}
void build()
{
    int hh=0,tt=0;
    for(int i=0;i<26;i++)
        if(tr[0][i])
        {
            q[tt++]=tr[0][i];
            add(0,tr[0][i]);
            sum[tr[0][i]]=sum[0]+st[tr[0][i]];
        }
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[tt++]=u;
                sum[u]=sum[fail[u]]+st[u];
            }
        }
    }
}
void query()
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'a';
        u=tr[u][t];
        cnt[u]++;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        id[i]=insert();
    }
    build();
    cin>>s;
    query();
    for(int i=idx-1;i>=0;i--)cnt[fail[q[i]]]+=cnt[q[i]];
    for(int i=1;i<=n;i++)cout<<cnt[id[i]]<<endl;
    return 0;
}