传送门

AC自动机理解的还是不够透彻，这道题没有想出来QAQ

这个如果真的不会玩用KMP打暴力很好想到。好吧其实不应该向kmp方面想，这个多字符串匹配显然是AC自动机。给出的字符串就是给你模拟了建立Trie树的过程。然后考虑根据每个点的fail指针建立fail树。

问$str_i$在$str_j$里出现了几次。显然就是问在Trie树里，有多少个$str_j$的元素指向$str_i$，在fail树里就转化成了在$str_i$的末尾元素所形成子树里有多少个$str_j$的元素。如果在线求这个就太麻烦了。

我们用树状数组离线搞。

再回到给出的那个字符串，其实那就是一个访问路径。首先在fail树上跑一遍dfs，求出来每个节点的入栈时间和出栈时间。然后按照字符串这个路径访问整个Trie树，每进入一个节点，把这个节点之前进栈的权值全部+1，每退出一个节点，把这个节点之前进栈的权值全部-1。每次访问到存在询问的节点。把进栈和出栈之间的权值累加就行了。

//BZOJ 2434//by Cydiater//2016.10.20#include <iostream>#include <cstdlib>#include <queue>#include <map>#include <ctime>#include <cstdio>#include <iomanip>#include <algorithm>#include <cstring>#include <string>#include <cmath>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}char s[MAXN];int id[MAXN],po=0,N,LEN,now=0,fail[MAXN],next[MAXN][30],fa[MAXN],cnt=0,q[MAXN],head,tail,LINK[MAXN],len,in[MAXN],out[MAXN],T=0,c[MAXN],ans[MAXN];struct edge{	int y,next;}e[MAXN];namespace solution{	inline int lowbit(int i){return i&(-i);}	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void add(int lim,int v){for(int i=lim;i<=T;i+=lowbit(i))c[i]+=v;}	inline int get(int lim){int tmp=0;for(int i=lim;i>=1;i-=lowbit(i))tmp+=c[i];return tmp;}	void init(){		scanf("%s",(s+1));		LEN=strlen(s+1);		N=read();		up(i,1,N){			int x=read()+LEN,y=read()+LEN;			insert(y,x);		}	}	void build(){		up(i,1,LEN){			if(s[i]==‘P‘)id[++po]=now;			else if(s[i]==‘B‘)now=fa[now];			else{				if(next[now][s[i]-‘a‘]==0)next[now][s[i]-‘a‘]=++cnt;				fa[next[now][s[i]-‘a‘]]=now;				now=next[now][s[i]-‘a‘];			}		}		head=1;tail=0;		up(i,0,25)if(next[0][i])q[++tail]=next[0][i];		for(;head<=tail;head++){			int now=q[head];			up(i,0,25){				int son=next[now][i];				if(son==0)next[now][i]=next[fail[now]][i];				else{					fail[son]=next[fail[now]][i];					q[++tail]=son;				}			}		}		up(i,1,cnt)insert(fail[i],i);	}	void dfs(int node){		in[node]=++T;		for(int i=LINK[node];i;i=e[i].next)dfs(e[i].y);		out[node]=++T;	}	void slove(){		dfs(0);now=0;cnt=0;		up(i,1,LEN){			if(s[i]==‘P‘){cnt++;				for(int j=LINK[cnt+LEN];j;j=e[j].next){					int y=id[e[j].y-LEN];					ans[j]=get(out[y])-get(in[y]-1);				}			}			else if(s[i]==‘B‘){				add(in[now],-1);				now=fa[now];			}else{				now=next[now][s[i]-‘a‘];				add(in[now],1);			}		}	}	void output(){		up(i,1,N)printf("%d\n",ans[i]);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	build();	slove();	output();	return 0;}

BZOJ2434: [Noi2011]阿狸的打字机