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
Solution
考虑一个暴力，我们想求的是第(x)个串在第(y)个串出现了多少次，那么我们先建出(AC)自动机，枚举第(y)个串的每一个位置，沿着(fail)指针往上跳，如果能正好跳到第(x)个串的末尾，那么就算一次。
那么考虑怎么优化这个过程，我们把(fail)指针反过来，建出(fail)树，那么问题就变成了(x)子树内有多少个属于(y)的点。
所以离线之后直接用树状数组维护子树信息即可。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 2e5+10;
char s[maxn];
int sta[maxn],top,cnt;
int tr[maxn][26],fail[maxn];
void make_fail() {
queue<int > q;
for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty()) {
int x=q.front();q.pop();
for(int i=0;i<26;i++)
if(tr[x][i]) fail[tr[x][i]]=tr[fail[x]][i],q.push(tr[x][i]);
else tr[x][i]=tr[fail[x]][i];
}
}
int head[maxn],tot,dfn[maxn],rev[maxn],dfn_cnt,sz[maxn];
struct edge{int to,nxt;}e[maxn<<1];
void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void ins(int u,int v) {add(u,v),add(v,u);}
void dfs(int x,int fa) {
dfn[x]=++dfn_cnt;sz[x]=1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to];
}
struct Binary_Indexed_Tree {
int t[maxn];
void modify(int x,int v) {for(;x<=cnt+1;x+=x&-x) t[x]+=v;}
int query(int x,int ans=0) {for(;x;x-=x&-x) ans+=t[x];return ans;}
}BIT;
#define pii pair<int,int >
#define vec vector<pii >
vec res[maxn];
int ans[maxn],n,m,pos[maxn];
void build() {
scanf("%s",s+1);n=strlen(s+1);
int pt=0;
for(int i=1;i<=n;i++) {
if(s[i]=='B') top--;
else if(s[i]=='P') pos[++pt]=sta[top];
else {
int &v=tr[sta[top]][s[i]-'a'];
if(!v) v=++cnt;
sta[++top]=v;
}
}
make_fail();
for(int i=1;i<=cnt;i++) ins(i,fail[i]);
dfs(0,-1);
}
void solve() {
top=0;
int pt=0;read(m);
for(int i=1,x,y;i<=m;i++) read(x),read(y),res[y].push_back(make_pair(x,i));
for(int i=1;i<=n;i++) {
if(s[i]=='B') BIT.modify(dfn[sta[top]],-1),top--;
else if(s[i]=='P') {
for(vec :: iterator j=res[++pt].begin();j!=res[pt].end();j++) {
int x=pos[(*j).first],id=(*j).second;
ans[id]=BIT.query(dfn[x]+sz[x]-1)-BIT.query(dfn[x]-1);
}
} else {
int v=tr[sta[top]][s[i]-'a'];
sta[++top]=v;BIT.modify(dfn[v],1);
}
}
for(int i=1;i<=m;i++) write(ans[i]);
}
int main() {
build();solve();
return 0;
}