Indie Album

Indie Album

/*
首先把需要匹配的串进行建树
然后把当前串在待匹配的串中进行行走
对呀，看那个是一个，那个是多个，就在哪里进行走
使用dfs进行走图

对待匹配的串进行建树
*/
#include <bits/stdc++.h>
using namespace std;
const int M=4e5+5;

int ch[M][26],fail[M],tag[M],tot;
void insert(string s,int id) {
    int p=0;
    for(int i=0;i<s.length();i++) {
        int v=s[i]-'a';
        if(ch[p][v]==0)ch[p][v]=++tot;
        p=ch[p][v];
    }
    tag[id]=p;
}

void build() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()) {
        int now=q.front();q.pop();
        for(int i=0;i<26;i++) {
            if(ch[now][i]) {
                fail[ch[now][i]]=ch[fail[now]][i];
                q.push(ch[now][i]);
            }
            else ch[now][i]=ch[fail[now]][i];
        }
    }
}

char s[M];
vector<int>v[M],f[M],g[M];

int L[M],R[M],id;
void dfs(int now,int fa) {
    L[now]=++id;
    for(auto to:g[now])
        if(to!=fa)dfs(to,now);
    R[now]=id;
}

int c[M];
int lowbit(int x) {
    return x&-x;
}
int query(int i) {
    int ans=0;
    while(i) {
        ans+=c[i];
        i-=lowbit(i);
    }
    return ans;
}
void add(int i,int v) {
    while(i<=id) {
        c[i]+=v;
        i+=lowbit(i);
    }
}
int query(int l,int r) {
    return query(r)-query(l-1);
}

int ans[M];
void calc(int id,int p) {
    if(id)p=ch[p][s[id]-'a'],add(L[p],1);
    for(auto i:f[id])ans[i]=query(L[tag[i]],R[tag[i]]);
    for(auto i:v[id])calc(i,p);
    add(L[p],-1);
}

int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++) {
        int op,j=0;cin>>op;
        if(op==2)cin>>j;
        v[j].push_back(i);
        cin>>s[i];
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++) {
        int x;cin>>x;
        string s;cin>>s;
        insert(s,i);
        f[x].push_back(i);
    }
    build();
    for(int i=1;i<=tot;i++)g[fail[i]].push_back(i);
    dfs(0,0);
    calc(0,0);
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}