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)。
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
3
1 2
1 3
2 3
Sample Output
1
0
HINT
1<=N<=10^5
Solution
是一道能让我们深刻理解AC自动机的好题。
输入很有意思。不是直接给n个字符串，而是给了一个打字的序列。
发现，如果暴力找所有的字符串的话，那么会n^2 爆炸
B，P有点意思。而且还是可以累积的。
所以，可以直接建出来一棵trie树。B就是返回father，打一个字母就是找一个son，P就是在这个点打标记。
怎么找？
暴力kmp匹配n^2
我们有多个模式串，肯定要想一想AC自动机
简化问题，假设一个主串T，多次询问一个S在T中出现次数？
trie毕竟是一个前缀集合，而S在T的出现位置，只能是若干个T[1...i]前缀的后缀。
如果我们走一遍T，把路径上点权++，代表这个点是一个T的前缀。
怎么判断S在某个前缀中出现过？
反过来，如果一个前缀T[1...i]中有S，那么从i不断跳fail指针，必然有一次会跳到S的结尾处。
而，AC自动机的fail是一棵树，如果按照fail的方向，是一棵内向树。
在fail树中，如果i是S结尾处的子树中的节点，那么意味着i跳fail可以到S结尾处。
所以，可以用一个树状数组维护dfn序，就可以查询S结尾处子树内权值和。就是出现次数。
如果主串T稍微动一下（末尾添加字符，删除末尾字符），也可以做到。直接把点权加上、删去即可。
而这个主串变动其实是在trie上dfs
每次dfs移动显然不划算。
所以离线询问，挂在所有T的末尾。
如果dfs到Ti的末尾，回答所有询问。即Sj的fail树子树的权值和。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+;
int n,m;
int sum;
struct node{
int sub,key;
int ans;
}que[N];
//trie&&AC machine
int ch[N][];
bool has[N][];
int tot;
int fail[N];
int fa[N];
vector<int>mem[N];
vector<int>exi[N];
int on[N];
char s[N];
void pre(){
int now=;
fa[]=;
for(int i=;i<=n;i++){
if(s[i]=='P'){
sum++;
on[sum]=now;
exi[now].push_back(sum);
}
else if(s[i]=='B'){
now=fa[now];
}
else{
int x=s[i]-'a';
if(!ch[now][x]) has[now][x]=,ch[now][x]=++tot,fa[ch[now][x]]=now;
now=ch[now][x];
}
}
}
//fail tree
struct edge{
int nxt,to;
}e[*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int dfn[N],dfn2[N];
int df;
void dfs(int x,int fa){
dfn[x]=++df;
for(int i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa)continue;
dfs(y,x);
}
dfn2[x]=df;
}
void build(){
queue<int>q;
for(int i=;i<=;i++){
if(has[][i]) fail[ch[][i]]=,add(,ch[][i]),q.push(ch[][i]);
}
while(!q.empty()){
int x=q.front();q.pop();
for(int i=;i<=;i++){
if(has[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];
add(ch[fail[x]][i],ch[x][i]);
q.push(ch[x][i]);
}
else{
ch[x][i]=ch[fail[x]][i];
}
}
}
}
//array tree
int f[N];
void upda(int x,int c){
for(;x<=n;x+=x&(-x)) f[x]+=c;
}
int query(int x){
int ret=;for(;x;x-=x&(-x)) ret+=f[x];return ret;
}
//ans
void sol(int x,int fa){
upda(dfn[x],);
for(int i=;i<mem[x].size();i++){
int son=on[que[mem[x][i]].sub];
int kk=query(dfn2[son])-query(dfn[son]-);
que[mem[x][i]].ans=kk;
}
for(int i=;i<=;i++){
if(has[x][i]){
sol(ch[x][i],x);
}
}
upda(dfn[x],-);
}
int main(){
scanf("%s",s+);
n=strlen(s+);
pre();
build();
dfs(,);//warning root is 0
scanf("%d",&m);
int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&que[i].sub,&que[i].key);
que[i].ans=;
mem[on[que[i].key]].push_back(i);
}
sol(,);
for(int i=;i<=m;i++){
printf("%d\n",que[i].ans);
}
return ;
}
upda：2019.3.27：
直接暴力fail树上线段树合并，就可以在线辣