http://www.lydsy.com/JudgeOnline/problem.php?id=2434
思路:建立fail树，并找出dfs序，那剩下要做的就是每次找到一个串的位置，然后询问它的区间里面有多少我当前串的节点，具体做法见代码。
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
struct edge{
int to,next,id;
}que[];
int fail[],sz,ch[][],root,num,hw,low[],dfn[];
char s[];
int pos[],id,fi[],first[],next[],tot,go[];
int fa[],ans[],V[],n,m;
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int v){
for (int i=x;i<=hw;i+=(i)&(-i)){
V[i]+=v;
}
}
int query(int x){
int res=;
for (int i=x;i;i-=(i)&(-i)){
res+=V[i];
}
return res;
}
void build(){
int now=;sz=;
for (int i=;i<n;i++){
if (s[i]=='P') pos[++id]=now;
else
if (s[i]=='B') now=fa[now];
else{
int k=s[i]-'a';
if (ch[now][k]==) ch[now][k]=++sz,fa[sz]=now;
now=ch[now][k];
}
}
}
void bfs(){
std::queue<int>Q;
for (int i=;i<;i++)
if (!ch[root][i]) ch[root][i]=root;
else if (ch[root][i]){
fail[ch[root][i]]=root;
Q.push(ch[root][i]);
}
while (!Q.empty()){
int now=Q.front();Q.pop();
for (int i=;i<;i++)
if (!ch[now][i]){
ch[now][i]=ch[fail[now]][i];
}else{
fail[ch[now][i]]=ch[fail[now]][i];
Q.push(ch[now][i]);
}
}
}
void dfs(int x){
dfn[x]=++hw;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
dfs(pur);
}
low[x]=++hw;
}
void solve(){
add(dfn[],);//root节点也算上
int sx=,now=;
for (int i=;i<n;i++){
if (s[i]=='P'){
sx++;
for (int j=fi[sx];j;j=que[j].next){
int pur=pos[que[j].to];
ans[que[j].id]+=query(low[pur])-query(dfn[pur]-);
}//询问dfs序区间里面有多少标记过的节点，有多少就代表y到root路径上的节点有多少能走到x的尾节点
}else
if (s[i]=='B') add(dfn[now],-),now=fa[now];//删除的时候去掉
else{
now=ch[now][s[i]-'a'];
add(dfn[now],);//走一步加一步
}
}
}
int main(){
scanf("%s",s);root=;
n=strlen(s);
build();
bfs();//建AC自动机
for (int i=;i<=sz;i++)
insert(fail[i],i);//建fail树
dfs();//找dfs序
scanf("%d",&m);
for (int i=;i<=m;i++){//把y相同的询问弄到一起
int x,y;
scanf("%d%d",&x,&y);
num++;
que[num].to=x;
que[num].next=fi[y];
que[num].id=i;
fi[y]=num;
}
solve();//统计答案
for (int i=;i<=m;i++)
printf("%d\n",ans[i]);
}