Description

阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。

经阿狸研究发现,这个打字机是这样工作的:

l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?
Input

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。
Output

输出m行,其中第i行包含一个整数,表示第i个询问的答案。
Sample Input
aPaPBbP

3

1 2

1 3

2 3

Sample Output
2

1

0
HINT

1<=N<=10^5

1<=M<=10^5

输入总长<=10^5

首先我们建出ac自动机,然后对于一组询问(x,y)就是从根到y字符串这条路径有多少点可以通过fail走到x节点,然后fail反向建出来的是一棵树(就叫fail树算了)

于是一组询问(x,y)就是从根到y字符串这条路径有多少点在x节点的子树中,于是我们处理出dfs序,我们就只要维护区间和就行了

对于多组询问我们就离线处理,按照他打字机的顺序遍历点,小写字母就在他的dfs序上+1,B就在现在这个节点的dfs序上-1,走到x单词的结束节点时处理询问(i,x)

 const
maxn=;
type
node=record
x,y,id:longint;
end;
var
go:array[..maxn,'a'..'z']of longint;
q:array[..maxn]of node;
ch:array[..maxn]of char;
e,p,fa,ll,rr,ans,fail,first,last,next,bit:array[..maxn]of longint;
n,cnt,tot,now,sum:longint;
s:ansistring; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; function nexts(x:longint;c:char):longint;
begin
if go[x,c]= then
begin
inc(cnt);go[x,c]:=cnt;
fa[cnt]:=x;ch[cnt]:=c;
end;
exit(go[x,c]);
end; procedure swap(var x,y:node);
var
t:node;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint);
var
i,j,y:longint;
begin
i:=l;j:=r;y:=q[(l+r)>>].x;
repeat
while q[i].x<y do inc(i);
while q[j].x>y do dec(j);
if i<=j then
begin
swap(q[i],q[j]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end; procedure dfs(x:longint);
var
i:longint;
begin
inc(sum);ll[x]:=sum;
i:=first[x];
while i<> do
begin
dfs(last[i]);
i:=next[i];
end;
rr[x]:=sum;
end; var
que:array[..maxn]of longint;
l,r:longint; procedure bfs;
var
i,j:longint;
c:char;
begin
que[]:=;l:=;r:=;
while l<=r do
begin
for c:='a' to 'z' do
if go[que[l],c]> then
begin
inc(r);
que[r]:=go[que[l],c];
end;
inc(l);
end;
for i:= to cnt do
begin
j:=que[i];c:=ch[j];j:=fail[fa[j]];
while (j<>) and (go[j,c]=) do
j:=fail[j];
fail[que[i]]:=go[j,c];
if fail[que[i]]=que[i] then fail[que[i]]:=;
insert(fail[que[i]],que[i]);
end;
end; function get(x:longint):longint;
begin
get:=;
while x> do
begin
inc(get,bit[x]);
x:=x-(x and (-x));
end;
end; procedure add(x,y:longint);
begin
while x<=sum do
begin
inc(bit[x],y);
x:=x+(x and (-x));
end;
end; procedure main;
var
i,j:longint;
begin
readln(s);now:=;
for i:= to length(s) do
begin
if s[i]='P' then
begin
inc(n);
e[n]:=i;
p[n]:=now;
end
else
if s[i]='B' then now:=fa[now]
else now:=nexts(now,s[i]);
end;
bfs;
dfs();
read(n);
for i:= to n do
read(q[i].y,q[i].x);
for i:= to n do q[i].id:=i;
sort(,n);
j:=;now:=;
for i:= to n do
begin
while j<e[q[i].x] do
begin
inc(j);
if s[j]='B' then
begin
add(ll[now],-);
now:=fa[now];
end
else
if s[j]<>'P' then
begin
now:=nexts(now,s[j]);
add(ll[now],);
end;
end;
ans[q[i].id]:=get(rr[p[q[i].y]])-get(ll[p[q[i].y]]-);
end;
for i:= to n do writeln(ans[i]);
end; begin
main;
end.
05-08 07:50