应该是某些答案算少了，但是我不知道哪里算少了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,len,x,y;
char s[1000005],t[1000005];
int head[1000005],nxt[2000005],target[2000005],tot;
void add(int x,int y){
	tot++;
	nxt[tot]=head[x];
	head[x]=tot;
	target[tot]=y;
}
struct node{
	int id,y;
};
vector<node> v[1000005];
int son[200005][26],tp[200005][26],fail[2000005],nd[2000005],ccnt;
queue<int> q;
void insert(char *s,int len,int id){
	int x=0;
	for(int i=1;i<=len;i++){
		if(!son[x][s[i]-'a']) son[x][s[i]-'a']=++ccnt;
		x=son[x][s[i]-'a'];
	}
	nd[id]=x;
}
void get_fail(){
	for(int i=0;i<26;i++){
		if(son[0][i]) q.push(son[0][i]);
	}
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(son[x][i]){
				fail[son[x][i]]=son[fail[x]][i];
				q.push(son[x][i]);
			}else{
				son[x][i]=son[fail[x]][i];
			}
		}
	}
}
int val[2000005],ls[2000005],rs[2000005],dcnt;
void pushup(int x){
	val[x]=val[ls[x]]+val[rs[x]];
}
void build(int l,int r,int &x){
	x=++dcnt;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls[x]);
	build(mid+1,r,rs[x]);
	pushup(x);
}
void modify(int l,int r,int pos,int k,int x){
	if(l==r){
		val[x]+=k;
		return; 
	}
	int mid=(l+r)>>1;
	if(pos<=mid) modify(l,mid,pos,k,ls[x]);
	else modify(mid+1,r,pos,k,rs[x]);
	pushup(x);
}
int query(int l,int r,int ql,int qr,int x){
	if(ql<=l && r<=qr) return val[x];
	int mid=(l+r)>>1,ans=0;
	if(ql<=mid) ans+=query(l,mid,ql,qr,ls[x]);
	if(qr>=mid+1) ans+=query(mid+1,r,ql,qr,rs[x]);
	return ans;
}
int size[1000005],dfn[10000005],low[100005],cnt;
void dfs_fail(int x,int fa){
	dfn[x]=++cnt;
	for(int i=head[x];i;i=nxt[i]){
		int y=target[i];
		if(y==fa) continue;
		dfs_fail(y,x);
	}
	low[x]=cnt;
}
int ans[1000005];
void dfs_trie(int x){
	modify(1,ccnt,dfn[x],1,1);
	if(v[x].size()){
		for(int j=0;j<v[x].size();j++){
			node tp=v[x][j];
			int id=tp.id,y=tp.y;
			ans[id]=query(1,ccnt,dfn[y],low[y],1); 
		}
	}
	for(int i=0;i<26;i++){
		if(!son[x][i]) continue;
		dfs_trie(son[x][i]);
	}
	modify(1,ccnt,dfn[x],-1,1);
} 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t+1;
	for(int i=1;t[i];i++){
		if(t[i]=='P'){
			n++;
			insert(s,len,n);
		}else if(t[i]=='B'){
			len--;
		}else{
			s[++len]=t[i];
		}
	}
	memcpy(tp,son,sizeof(tp));
	get_fail();
	memcpy(son,tp,sizeof(son));
	cout<<endl;
	for(int i=1;i<=ccnt;i++){
		add(fail[i],i);
		add(i,fail[i]);
		//cout<<i<<" "<<fail[i]<<endl;
	}
	dfs_fail(0,0);
	build(1,ccnt,x);
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[nd[y]].push_back({i,x});
	}
	dfs_trie(0); 
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
/*
a
aa
ab
aba
ba
baa
bb
bba
*/