http://www.zybbs.org/JudgeOnline/problem.php?id=2434

做了4小时……最后发现问题在于我的AC自动机模板是错的……一直没怀疑……555这么弱怎么活……

不过最后1Y+Rank1，代码长度也是最短的（DYH大神1.9KB+），还是比较满意的结果！

这题同时考察了AC自动机和维护DFS序两个点，如果你对AC自动机理解得好的话一下子就能看出怎么做。同时ymNOI虐场的CLJ大神……

首先粗略地介绍一下AC自动机，这是一个在字母表较小的情况下线性的多串匹配算法。把所有目标串构成一个trie树，对于每个节点，记录一个fail指针表示如果匹配失败，则最近能跳到哪里。比如x的fail指向y，则说明root..x这个字符串的后缀是根..y，且对于所有root..x的后缀，root..y是最长的一个在trie中的。

构出trie后，点x的fail指针可以通过它父亲f的fail指针算出来。假设x对应字符c，依次检查f->fail,f->fail->fail,f->fail->fail->fail……root，如果有一个存在字符为c的儿子t，则x->fail=t，否则x->fail=root，这个还是很好想的……

问题在于处理顺序，我就是这里2X了。正确方法应该是弄个队列，一开始只有root，每次处理完一个点后把这个点所有儿子加进来即可。至于为什么……呃……不知道 T^T

对于这题，先构出AC自动机。然后对于一个询问(x,y)，暴力的做法是，枚举root..y上的每一个点作为终点（即这个点为最后一个字符），不断取fail指针，如果能跳到x，则说明这个位置匹配成功，这个应该很好理解。

考虑能跳到x的节点，如果将fail指针反过来，这就是一棵树，叫做fail tree。在fail tree中，能跳到x的节点就是x的子树节点！只要找出这些节点中root..y中的节点有几个就可以了。

离线查询子树信息可以用DFS序来做，一个点的子树在DFS序中是一段，可以用BIT等维护，不说了。遍历整个trie，当询问到节点y时，对于每个询问(x,y)，我们需要知道在fail tree中，x的子树节点中有几个是在root..y中的。即在遍历到y时，BIT中保存的是root..y这些节点的信息，这些点每个点的值是1，其它点是0。那么只要遍历一个点的儿子之前将其设为1，遍历完改回0就可以了，询问即是询问一段的和。

如果不懂的话先自己想想……也可以在下面留言恩。这个还是比较麻烦的，我想了好久，最重要的是要注意，这里有trie和fail tree两个树，其中trie是用来遍历和构造fail指针的，fail tree只需要记录它的DFS序，然后更新都是在DFS序上做手脚。

#include <stdio.h>
#define maxn 100010
#define T struct trie
#define E struct edge
#define Q struct qz
T{T*f,*fail,*c[26];int id}t,stt[maxn],*que[maxn]={&t};
E{E*next;int y}*map[maxn],st[maxn];
Q{Q*next;int x,ans}*q[maxn],stq[maxn];
int id[maxn],s[maxn][2],n,a[maxn],bq=-1,eq=1;
char str[2000000],*p=str;
inline void I(x,y){for(;x<=n;x+=x&-x)a[x]+=y;}
inline S(x){int t=0;for(;x;x-=x&-x)t+=a[x];return t;}
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}void Init(x){E*p=map[x];for(s[x][0]=++n;p;p=p->next)Init(p->y);s[x][1]=n;}
void Travel(T*x){
	Q*p=q[x->id];int i=-1;
	for(;p;p=p->next)p->ans=S(s[p->x][1])-S(s[p->x][0]-1);
	while(++i!=26)if(x->c[i]){
		I(s[x->c[i]->id][0],1);
		Travel(x->c[i]);
		I(s[x->c[i]->id][0],-1);
	}
}main(){
	int m=1,i=0,y;T*f=&t;fread(p,1,2000000,stdin);p--;
	while(*++p>0)if(*p=='P')id[i++]=f->id;
	else if(*p=='B')f=f->f;
	else if(*p<'a'||*p>'z')break;
	else if(f->c[y=*p-'a'])f=f->c[y];
	else(f->c[y]=stt+m)->f=f,(f=f->c[y])->id=m++;
	while(++bq!=eq)for(i=-1;++i!=26;)if(que[bq]->c[i]){
		for(f=que[bq]->fail;f&&!f->c[i];)f=f->fail;
		f=(que[eq]=que[bq]->c[i])->fail=f?f->c[i]:&t;
		st[eq].y=que[eq]->id;st[eq].next=map[f->id];map[f->id]=st+eq++;
	}for(Init(0),i=m=getint();i--;q[y]=stq+i){
		stq[i].x=id[getint()-1];
		stq[i].next=q[y=id[getint()-1]];
	}for(Travel(&t);m--;)printf("%d\n",stq[m].ans);
	return 0;
}

• inline
• block