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

Source

Trie



这题一看就能看出是AC自动机，那么关键就是怎么快速匹配

构架一颗AC自动机的fail的树，然后就可以知道这棵树的dfs序。

用树状数组维护dfs序，就可以了

对于每一个询问x,y，查询自动机上从root到y的每一个节点，然后沿着fail指针走，看看是否能走到x的起始点。

__attribute__((__optimize__("-O2"))) //这里是为了速度开的O2优化


#include<algorithm>
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<map>
#include<set>
using namespace std;
int n,m,cnt;
int T,l[100005],r[100005],t[200005];
int ll[100005],llq[100005],p[100005],ans[100005];
char ch[100005];

__attribute__((__optimize__("-O2"))) inline int query(int x);
__attribute__((__optimize__("-O2"))) inline void insert(int u,int v);
__attribute__((__optimize__("-O2"))) void dfs(int x);
__attribute__((__optimize__("-O2"))) inline void add(int x,int val);
__attribute__((__optimize__("-O2"))) inline int Readint();


struct fail_tree
{
	int to,next,v;
}e[100005],que[100005];

struct AC_auto
{
	int cnt;
	int f[100005],fail[100005],next[100005][26];
	int q[100005];
	__attribute__((__optimize__("-O2"))) inline AC_auto()
	{
		cnt = 1;
		for(int i = 0; i < 26; i ++)
			next[0][i] = 1;
	}
	__attribute__((__optimize__("-O2"))) void build()
	{
		int now = 1,id = 0;
		for(int i = 0; i < n; i ++)
			if(ch[i] == 'P')p[++ id] = now;
			else if(ch[i] == 'B')now = f[now];
			else 
			{
				if(!next[now][ch[i] - 'a'])
				{
					next[now][ch[i] - 'a'] = ++ cnt;
					f[cnt] = now;
				}
				now = next[now][ch[i] - 'a'];
			}
	}
	__attribute__((__optimize__("-O2"))) inline void buildfail()
	{
		int head = 0,tail = 1;
		fail[1] = 0;
		q[0] = 1;
		while(head < tail)
		{
			int now = q[head];
			head ++;
			for(int i = 0; i < 26; i ++)
				if(next[now][i])
				{
					int v = next[now][i];
					int k = fail[now];
					while(!next[k][i])k = fail[k];
					fail[v] = next[k][i];
					q[tail ++] = v;
				}
		}
	}
	__attribute__((__optimize__("-O2"))) inline void solve()
	{
		int now = 1,id = 0;
		add(l[1],1);
		for(int i = 0; i < n; i ++)
			if(ch[i] == 'P')
			{
				id ++;
				for(int x = llq[id]; x; x = que[x].next)
				{
					int t = p[que[x].to];
					ans[x] = query(r[t]) - query(l[t] - 1);
				}
			}
			else if(ch[i] == 'B') add(l[now],-1),now = f[now];
			else now = next[now][ch[i] - 'a'], add(l[now],1);;
	}	
}ac;
int main()
{
	scanf("%s",ch);
	n = strlen(ch);
	ac.build();
	ac.buildfail();
	for(int i = 1; i <= ac.cnt; i ++)
		insert(ac.fail[i],i);
	m = Readint();
	for(int i = 1; i <= m; i ++)
    {
		int x = Readint(), y = Readint();
		que[i].next = llq[y];
		llq[y] = i;
		que[i].to = x;
	}
	dfs(0);
	ac.solve();
	for(int i = 1; i <= m; i ++)printf("%d\n",ans[i]);
	return 0;
}

__attribute__((__optimize__("-O2"))) inline void add(int x,int val)
{
	for(int i = x; i <= T; i += i & -i )t[i] += val;
}
__attribute__((__optimize__("-O2"))) inline int query(int x)
{
	int sum = 0;
	for(int i = x; i; i -= i & -i )sum += t[i];
	return sum;
}
__attribute__((__optimize__("-O2"))) inline void insert(int u,int v)
{
	e[++ cnt].to = v;
	e[cnt].next = ll[u];
	ll[u] = cnt;
}
__attribute__((__optimize__("-O2"))) void dfs(int x)
{
	l[x] = ++ T;
	for(int i = ll[x]; i; i = e[i].next)
		dfs(e[i].to);
	r[x] = ++ T;
}
__attribute__((__optimize__("-O2"))) inline int Readint()
{
	int x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')ch=getchar();
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
	return x;
}