题意:给一颗字典树,m次查询,每次给出一个字符串,问你该字符串是字典树上多少串的后缀

题解:字典树求广义sam,每次把查询串在sam上跑一遍,最后到达的点的sz就是答案,中途没法走了,就是没有出现过

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize(4)

//#pragma GCC optimize("unroll-loops")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>

#define fi first

#define se second

#define db double

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define ld long double

//#define C 0.5772156649

//#define ls l,m,rt<<1

//#define rs m+1,r,rt<<1|1

#define pll pair<ll,ll>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define ull unsigned long long

//#define base 1000000000000000000

#define fin freopen("a.txt","r",stdin)

#define fout freopen("a.txt","w",stdout)

#define fio ios::sync_with_stdio(false);cin.tie(0)

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}

inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}

template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}

template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}

inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}

inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}

using namespace std;

const ull ba=233;

const db eps=1e-5;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=1000000+10,maxn=1000000+10,inf=0x3f3f3f3f;

char s[N];

struct SAM{

    int last,cnt;

    int ch[N<<1][26],fa[N<<1],l[N<<1],sz[N<<1];

    int c[N<<1],a[N<<1];

    int ins(int y,int x)

    {

        last=y;

        int p=last,np=++cnt;last=np;l[np]=l[p]+1;

        for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np;

        if(!p)fa[np]=1;

        else

        {

            int q=ch[p][x];

            if(l[q]==l[p]+1)fa[np]=q;

            else

            {

                int nq=++cnt;l[nq]=l[p]+1;

                memcpy(ch[nq],ch[q],sizeof ch[q]);

                fa[nq]=fa[q];fa[q]=fa[np]=nq;

                for(;ch[p][x]==q;p=fa[p])ch[p][x]=nq;

            }

        }

        sz[np]=1;

        return last;

    }

    void build()

    {

        cnt=last=1;

    }

    void topo()

    {

        for(int i=1;i<=cnt;i++)c[l[i]]++;

        for(int i=1;i<=cnt;i++)c[i]+=c[i-1];

        for(int i=1;i<=cnt;i++)a[c[l[i]]--]=i;

    }

    void gao()

    {

        topo();

        for(int i=cnt;i;i--)sz[fa[a[i]]]+=sz[a[i]];

    }

    void cal()

    {

        int len=strlen(s+1),now=1;

        for(int i=len;i>=1;i--)

        {

            if(ch[now][s[i]-'A'])now=ch[now][s[i]-'A'];

            else

            {

                puts("0");

                return ;

            }

        }

        printf("%d\n",sz[now]);

    }

}sam;

int a[N],id[N];

struct Tire{

    vector<int>v[N];

    void bfs()

    {

        queue<int>q;q.push(0);id[0]=1;

        while(!q.empty())

        {

            int u=q.front();q.pop();

            for(int i=0;i<v[u].size();i++)if(v[u][i])

            {

                id[v[u][i]]=sam.ins(id[u],a[v[u][i]]);

                q.push(v[u][i]);

            }

        }

    }

}t;

int main()

{

    int n,m;scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        int x;scanf("%s%d",s,&x);

        t.v[x].pb(i);a[i]=s[0]-'A';

    }

    sam.build();

    t.bfs();

    sam.gao();

    while(m--)

    {

        scanf("%s",s+1);

        sam.cal();

    }

    return 0;

}

/********************

********************/