利用了bzoj3172提到的性质，x串在y串中的出现的次数即为在fail树上以x结尾节点为根的子树中有多少个节点在y串上
所以很明显我们要离线解决，我们先把询问按y分类存起来
然后我们顺着操作顺序来，出现一个字符就把fail树上对应节点标为1，删除之后就改为0；
当一个串输出之后，我们就统计跟他有关的询问（查询x串结尾节点子树和）
这种问题显然用dfs序+树状数组解决
const maxn=;
type node=record
y,next:longint;
end; var i,j,n,m,len,tot,all,k,ll,rr,num,x,y,p:longint;
t:array[..maxn,'a'..'z'] of longint;
q,pre,f,v,l,d,h,r,h2,ans,st,sum:array[..maxn] of longint;
g,g2:array[..maxn] of node;
c:char;
s:array[..maxn] of char; procedure add(x,y:longint);
begin
inc(num);
g[num].y:=y;
g[num].next:=h[x];
h[x]:=num;
end; procedure ac;
begin
fillchar(q,sizeof(q),);
ll:=;
rr:=;
for c:='a' to 'z' do
if t[,c]> then
begin
add(,t[,c]);
inc(rr);
q[rr]:=t[,c];
end;
while ll<>rr do
begin
inc(ll);
i:=q[ll];
for c:='a' to 'z' do
if t[i,c]> then
begin
k:=t[i,c];
inc(rr);
q[rr]:=k;
j:=f[i];
while (j>) and (t[j,c]=) do j:=f[j];
f[k]:=t[j,c];
add(t[j,c],k);
end;
end;
end; procedure dfs(x:longint);
var p:longint;
begin
inc(tot);
l[x]:=tot;
p:=h[x];
while p<> do
begin
dfs(g[p].y);
p:=g[p].next;
end;
r[x]:=tot;
end; procedure ins(x,y:longint);
begin
g2[i].y:=y;
g2[i].next:=h2[x];
h2[x]:=i;
end; procedure change(x,y:longint);
begin
while x<=tot do
begin
inc(sum[x],y);
inc(x,x and -x);
end;
end; function get(x:longint):longint;
begin
get:=;
while x> do
begin
inc(get,sum[x]);
dec(x,x and -x);
end;
end; procedure main;
begin
readln(n);
for i:= to n do
begin
readln(x,y);
ins(y,x);
end;
j:=;k:=;m:=;
for i:= to len do
begin
case s[i] of
'B':begin change(l[st[k]],-);dec(k);j:=pre[j];end;
'P':
begin
inc(m);p:=h2[m];
while p<> do
begin
ans[p]:=get(r[d[g2[p].y]])-get(l[d[g2[p].y]]-);
p:=g2[p].next;
end;
end;
else begin
j:=t[j,s[i]];
inc(k);st[k]:=j;
change(l[j],);
end;
end;
end;
for i:= to n do writeln(ans[i]);
end; begin
j:=;
while not eoln do
begin
inc(len);
read(s[len]);
case s[len] of
'B':begin j:=pre[j];end;
'P':begin inc(tot);d[tot]:=j;v[j]:=;end;
else begin
if t[j,s[len]]= then
begin
inc(all);
t[j,s[len]]:=all;
pre[all]:=j;
end;
j:=t[j,s[len]];
end;
end;
end;
readln;
ac;
tot:=;
dfs();
main;
end.