[WF2019]First of Her Name

The first line of input contains two integers $n$ and $k$ , where $n (1 ≤ n ≤ 10^6)$ is the total number of Royal Ladies and $k (1 ≤ k ≤ 10^6)$ is the number of query strings.
Then follow $n$ lines describing the Royal Ladies. The $i^{th}$ of these lines describes the Royal Lady numbered $i$ , and contains an uppercase letter $c_i (‘A’–‘Z’)$ and an integer $p_i$ , where $c_i$ is the first letter of the name of Lady $i$ , and $p_i$ ( $p_1 = 0$ and $1 ≤ p_i < i$ for $i > 1$ ) is the number of her mother (or 0, in the case of the First Lady). All the names are unique.
The remaining $k$ lines each contain one nonempty query string, consisting only of uppercase letters. The sum of the lengths of the query strings is at most $10^6$

C++(clang++ 11.0.1) 解法, 执行用时: 2088ms, 内存消耗: 224388K, 提交时间: 2022-09-07 17:12:12

#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;
}

C++(g++ 7.5.0) 解法, 执行用时: 882ms, 内存消耗: 228084K, 提交时间: 2022-08-19 18:23:40

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int tire[N][26],stop[N],tot=0;
int fail[N],q[N],hh,tt;
int cnt[N],id[N];
int insert(string &s)
{
	int rt=0;
	for(int i=s.size()-1;i>=0;i--)
	{
		int tmp=s[i]-'A';
		if(!tire[rt][tmp])
			tire[rt][tmp]=++tot;
		rt=tire[rt][tmp];
	}
	stop[rt]=1;
	return rt;
}
void build()
{
	hh=tt=0;
	for(int i=0;i<26;i++)
	{
		if(tire[0][i])
		{
			q[tt++]=tire[0][i];
		}
	}
	while(hh!=tt)
	{
		int x=q[hh++];
		for(int i=0;i<26;i++)
		{
			int &p=tire[x][i];
			
			if(!p)
				p=tire[fail[x]][i];
			else 
			{
				fail[p]=tire[fail[x]][i];
				q[tt++]=p;
			}
		}
	}
}
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		char ch;
		int last;
		cin>>ch>>last;
		tire[last][ch-'A']=++tot;
		cnt[tot]++;
	}
	for(int i=1;i<=k;i++)
	{
		string s;
		cin>>s;
		id[i]=insert(s);
	}
	build();
	for(int i=tot;i>=0;i--)
	{
		cnt[fail[q[i]]]+=cnt[q[i]];
	}
	for(int i=1;i<=k;i++)
	{
		cout<<cnt[id[i]]<<'\n';
	}
}

详情