题意
给定 \(n\) 个字符串，\(m\) 次询问一个字符串 \(x\) 在另一个字符串 \(y\) 的出现次数。
\(1 \leq n,m \leq 10^5\)。
思路
要解决多个字符串的问题，不难想到 AC 自动机。
根据 AC 自动机上 fail 数组的性质，即以 \(fail_i\) 所结尾的字符串一定是以 \(i\) 结尾的字符串的后缀。
一个字符串的所有子串可以表示为它所有后缀子串的所有前缀子串，而在 trie 树上，以 \(i\) 结尾的字符串一定是以 \(i\) 子树内任意节点结尾的字符串的前缀。
不难发现，现在问题就转化为了求 trie 数上从根节点到 \(x\) 所对应的结尾节点这条路径上，有多少个节点在 fail 树上是 \(y\) 子树内的节点。
而求一个子树内的节点，就可以用到dfs序。将询问离线，维护从根节点到 \(x\) 节点路径上点的dfs序，也就是单点询问 $$+$ 区间查询，可以用到树状数组。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int c[N],in[N],out[N],num,Q[N],fa[N],cpy[N][26],id[N],tot=1,tr[N][26],fail[N],h[N],ans[N],idx,n,m;char s[N];
vector<int>ask[N];
struct query{int x,y;}q[N];
struct edge{int v,nex;}e[N];
void add(int u,int v){e[++idx]=edge{v,h[u]};h[u]=idx;}
void build_AC()
{
fail[1]=1;int hh=0,tt=-1;
for(int i=0;i<26;i++) if(tr[1][i]) Q[++tt]=tr[1][i],fail[tr[1][i]]=1;else tr[1][i]=1;
while(hh<=tt)
{
int u=Q[hh++];
for(int i=0;i<26;i++)
{
int &v=tr[u][i];
if(!v) v=tr[fail[u]][i];
else Q[++tt]=v,fail[v]=tr[fail[u]][i];
}
}
}
void dfs(int u)
{
in[u]=++num;
for(int i=h[u];i;i=e[i].nex) dfs(e[i].v);
out[u]=num;
}
void update(int x,int k){while(x<=n) c[x]+=k,x+=x&-x;}
int query(int x){int res=0;while(x) res+=c[x],x-=x&-x;return res;}
void solve(int u)
{
update(in[u],1);
for(int i=0;i<ask[u].size();i++) ans[ask[u][i]]=query(out[id[q[ask[u][i]].x]])-query(in[id[q[ask[u][i]].x]]-1);
for(int i=0;i<26;i++) if(cpy[u][i]) solve(cpy[u][i]);
update(in[u],-1);
}
int main()
{
scanf("%s",s+1);n=strlen(s+1);scanf("%d",&m);int now=1,cnt=0;
for(int i=1;i<=n;i++)
{
if('a'<=s[i]&&s[i]<='z')
{
int v=s[i]-'a';
if(!tr[now][v]) tr[now][v]=++tot,fa[tot]=now;
now=tr[now][v];
}
else if(s[i]=='P') id[++cnt]=now;
else now=fa[now];
}
memcpy(cpy,tr,sizeof(tr));build_AC();for(int i=2;i<=tot;i++) add(fail[i],i);dfs(1);
for(int i=1;i<=m;i++) scanf("%d%d", &q[i].x,&q[i].y),ask[id[q[i].y]].push_back(i);solve(1);
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}