题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2434

题目分类：字符串，AC自动机，DFS序

题意：

给出一个支持向内存的最后一位的后面添加一个字符，删除内存中最后一个字符，打印出内存中字符串的打印机的操作序列，每次询问第x个被打印出来的字符串在第y个被打印出来的字符串中出现了几次

题解：

因为是多串匹配所以先构建AC自动机。

可以发现在AC自动机中因为fail指针的定义，被一个V节点的fail指针连到的节点表示的字符串是V表示的字符串的后缀，所以对于每一个询问只要对y的路径上的每一个节点沿着fail指针走，走到几次x节点答案就是几次。

可以逆向思维考虑，从x节点沿着fail指针反向走，走到多少个y路径上的点就是答案，很容易发现fail指针反向之后构成的图是一棵树，x节点能走到的节点是他的子树，问题转化为链上修改子树查询。

可以考虑离线，按照操作序列来即时修改可以把问题转化为单点修改子树查询，DFS序可以轻松解决。

程序：

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
inline int lowbit(int x)
{
	return (x&(-x));
}
int m,x1,x2,qst[120000],qed,ed,st[120000];
struct quer
{
	int next,id,to;
}qu[120000];
int ans[120000];
inline void addquery(int x,int y,int idx)
{
	qed++;
	qu[qed].to=x;
	qu[qed].id=idx;
	qu[qed].next=qst[y];
	qst[y]=qed;
}
struct node
{
	int to,next;
}g[120000];
inline void add(int x,int y)
{
	ed++;
	g[ed].to=y;
	g[ed].next=st[x];
	st[x]=ed;
}
int lef[120000],cur,rig[120000],pos[120000];
inline void dfs(int x,int fat)
{
	cur++;
	lef[x]=cur;
	for (int i=st[x];i!=0;i=g[i].next)
	{
		if(g[i].to!=fat)
		{
			dfs(g[i].to,x);
		}
	}
	rig[x]=cur;
}struct bit
{
	int a[120000];
	inline void edit(int x,int y)
	{
		while (x<=120000)
		{
			a[x]+=y;
			x+=lowbit(x);
		}
	}
	inline int query(int x)
	{
		int ss=0;
		while (x>0)
		{
			ss+=a[x];
			x-=lowbit(x);
		}return ss;
	}
}sgt;
int num;
char str[120000];
struct ac
{
	int a[120000][26],fail[120000],end[120000],fat[120000],siz;
	ac()
	{
		siz=1;
	}
	inline void build()
	{
		int le=strlen(str+1),tmp=1;
		for (int i=1;i<=le;i++)
		{
			if(str[i]=='B')
			{
				tmp=fat[tmp];
			}
			else if(str[i]=='P')
			{
				num++;
				end[tmp]=num;
				pos[num]=tmp;
			}
			else
			{
				int tp=str[i]-'a';
				if(a[tmp][tp]==0)
				{
					siz++;
					a[tmp][tp]=siz;
					fat[a[tmp][tp]]=tmp;
				}
				tmp=a[tmp][tp];
			}
		}
	}
	inline void buildauto()
	{
		queue<int>q;
		q.push(1);
		int x1;
		fail[1]=1;
		while (!q.empty())
		{
			x1=q.front();
			if(x1!=1)add(fail[x1],x1);
			printf("%d %d\n",x1,fail[x1]);
			q.pop();
			for (int i=0;i<26;i++)
			{
				if(a[x1][i]!=0)
				{
					if(x1==1)
					{
						fail[a[x1][i]]=1;
					}
					else
					{
						int tem=fail[x1];
						while (tem!=1&&a[tem][i]==0)
						{
							tem=fail[tem];
						}
						if(a[tem][i]!=0)fail[a[x1][i]]=a[tem][i];
						else fail[a[x1][i]]=1;
					}
					q.push(a[x1][i]);
				}
			}
		}
	}
}acsgt;
inline void print()
{
	for (int i=1;i<=5;i++)
	{
		printf("%d ",sgt.query(i+1)-sgt.query(i));
	}printf("\n");
	for (int i=1;i<=5;i++)
	{
		printf("%d %d\n",lef[i],rig[i]);
	}
	for (int i=1;i<=5;i++)
	{
		printf("%d %d\n",pos[i],acsgt.end[i]);
	}
}
inline void solve()
{
	int tmp=1,le=strlen(str+1);;
	for (int i=1;i<=le;i++)
	{
		if(str[i]=='B')
		{
			sgt.edit(lef[tmp],-1);
			tmp=acsgt.fat[tmp];
		}
		else if(str[i]=='P')
		{
			int x1=acsgt.end[tmp];
			for (int i=qst[x1];i!=0;i=qu[i].next)
			{
				ans[qu[i].id]=sgt.query(rig[pos[qu[i].to]])-sgt.query(lef[pos[qu[i].to]]-1);
			//	printf("%d--------%d\n",qu[i].id,ans[qu[i].id]);
			}
		}
		else
		{
			tmp=acsgt.a[tmp][str[i]-'a'];
			sgt.edit(lef[tmp],1);
		}
	//	printf("%d %d --\n",i,tmp);
	//	print();
	}
}
int main()
{
	scanf("%s",str+1);
	acsgt.build();
	acsgt.buildauto();
	dfs(1,0);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d %d",&x1,&x2);
		addquery(x1,x2,i);
	}
	solve();
	for (int i=1;i<=m;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}