题目描述

给我们n个名字(字符串),这些串遵循一个规律,第i个名字是它前面某个名字在前面加一个字母,第一个名字是在空串前面加一个字母.
然后给我们m个询问(感兴趣的名字),问有多少个名字是询问中感兴趣的字符串的前缀.

样例

输入

10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY

输出

2
2
1
1
0

分析

从问题出发,问我们有多少个名字是感兴趣的名字的前缀,如果我们把所有名字和询问反转,即问我们有多少名字是感兴趣的名字的后缀,这很符合AC自动机.当我们把所有名字反转后,那新添加一个名字也就是在当前存在的节点后面在添加一个节点,(保证了没有重复名字),然后我们把问题离线,也就是把所有询问存下来,并且把询问串插入Trie树中,但是不打终止标记.求有多少名字是感兴趣的名字的后缀也就是求该询问串所在的节点的fail树的子树中有多少终止标记,将标记从下往上推即可.

离线+AC自动机

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M = 2e6+10;
int tr[M][26],idx;
int fail[M],q[M];
int id[N];
int n,m;
char s[N];
int cnt[M];
int insert()
{
    int u=0;
    for(int i=strlen(s)-1;i>=0;i--)
    {
        int t=s[i]-'A';
        if(!tr[u][t])tr[u][t]=++idx;
        u=tr[u][t];
    }
    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];
    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;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char c;
        int p;
        cin>>c>>p;
        tr[p][c-'A']=++idx;
        cnt[idx]=1;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        id[i]=insert();
    }
    build();
    for(int i=idx-1;i>=0;i--)cnt[fail[q[i]]]+=cnt[q[i]];
    for(int i=1;i<=m;i++)
    {
        cout<<cnt[id[i]]<<endl;
    }
    return 0;
}