题意：一开始是个空串s,有三种操作：（1.末尾加一个字符 2.末尾减一个字符 3.存储该字符串）

思路：

一开始在trie树上动态加点很好处理，3操作的时候记录一下此时trie树上的pos，同时记录dep,fa后面有用。

建AC自动机，因为这道题的大致思路还是：y包含于x,则x的所有前缀（trie树上的祖先节点）对应的后缀中存在y的个数和。

因此只要y的祖先节点在fail树上对应++。然后再算x的子树和。（这里映射到dfs序上，显然树状数组维护，我一开始tm写了线段树）

询问先按y排序，这样就可以O(|S|)跳串，具体我是ylst和y往LCA(ylst,y)上跳。过程中ylst删除贡献，y加入贡献。

我加快读,O2跑到了第一页：

code:

#include
using namespace std;
const int N=1e6+5;
char s[N];
int sz,n,m,pos[N],ans[N];
struct query {int x,y,id;}Q[N];
bool cmp(query u,query v) {return u.yp1=buf,p2=buf,obuf[1000000],p3=obuf; #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:p1++ #define putchar(x) (p3-obuf<1000000)?(p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,p3++=x) template
inline void read(register item &x)
{
x=0;register char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); } struct AC { int c[N],fa[N],fail[N],go[N][27],nw,nd,Q[N],hd,tl,nxt[N],to[N],head[N],ecnt,In[N],Out[N],dep[N],Time,y0,rt; void Update(int x,int d) {for(;x<=Time;x+=x&(-x))c[x]+=d;} int Sum(int x) {int res=0;for(;x;x-=x&(-x))res+=c[x];return res;} AC() {nw=nd=tl=Time=y0=0;hd=1;} void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;} void Add(int x) {if(!go[nw][x]){go[nw][x]=++nd;fa[nd]=nw;dep[nd]=dep[nw]+1;}nw=go[nw][x];} void Del() {nw=fa[nw];} void Get(int &p) {p=nw;} void init(int u) { In[u]=++Time; for(int i=head[u];i;i=nxt[i]) { int v=to[i];init(v); } Out[u]=Time; } void gt_fail() { for(int j=0;j<26;j++)if(go[0][j])Q[++tl]=go[0][j]; while(hd<=tl) { int u=Q[hd++]; for(int j=0;j<26;j++) { int v=go[u][j]; if(v) fail[v]=go[fail[u]][j],Q[++tl]=v; else go[u][j]=go[fail[u]][j]; } } for(int i=1;i<=nd;i++) add_edge(fail[i],i); // for(int i=1;i<=nd;i++) printf("+ %d %d\n",fail[i],i); init(0); } void solve(int id,int x,int y) { int lst=y; while(y!=y0) { if(dep[y]>dep[y0]) {Update(In[y],1);y=fa[y];}
else {Update(In[y0],-1);y0=fa[y0];}
//y0 used to add lca(y,y0)
}
ans[id]=Sum(Out[x])-Sum(In[x]-1);
y0=lst;
}
}A;
int main() {
// freopen("dd.in","r",stdin);
char c;
while((c=getchar())!='\n') {
if(c=='P') {++n;A.Get(pos[n]);}
else if(c=='B') A.Del();
else A.Add(c-'a');
}
A.gt_fail();
read(m);
for(int i=1;i<=m;i++) read(Q[i].x),read(Q[i].y),Q[i].id=i;
sort(Q+1,Q+1+m,cmp);
for(int i=1;i<=m;i++) {A.solve(Q[i].id,pos[Q[i].x],pos[Q[i].y]);}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}