Vexoben
May 5, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2434
题意
有n组操作，m组询问，每组操作是：
c ： c为一个小写字母，表示在打字板的末尾打上c
‘B’ : 删除打字板最后一个字母
‘P’ : 将打字板中的字符串写下，打字板中的字符不会消失
每组询问形如(x,y)，表示询问第x个打下的字符串在第y个打下的字符串中出现的次数。
n,m<=100000
题解
显然一棵trie树就可以存下所有的字符串。
然后我们将AC自动机建出来。一个串x在串y中出现，必然有x是y某个前缀的后缀。而AC自动机的fail指针又恰是“最长前缀匹配后缀”，这意味着如果x是y的子串，当且仅当存在y的一个前缀节点不停跳fail指针能到x。
那么每组询问(x,y)，就等价于询问在fail树上以x为根的子树中有多少个y的前缀节点。
将树上询问转换为在dfs序上的询问。
将询问离线，再模拟一次trie的插入过程，并使根到这个节点的路径上节点权值为1，其余为0。当插入到节点y时查询x子树在dfs序上对应区间的权值和即可，这需要用树状数组维护一下。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<time.h>
#include<vector>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define R register
#define LL long long
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
char s[N];
int n,m,l,rt,tot,tim,ans[N];
int ord[N],ch[N][26],fail[N],fa[N],ent[N],lef[N],bit[N];
queue<int> Q;
vector<int> son[N];
vector<pair<int,int> > qy[N];
void insert() {
int x=rt;
for (int i=1;i<=l;i++) {
if (s[i]=='B') x=fa[x];
else if (s[i]=='P') ord[++n]=x;
else {
if (!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++tot,fa[tot]=x;
x=ch[x][s[i]-'a'];
}
}
}
void GetFail() {
fail[rt]=rt;
for (int i=0;i<26;i++)
if (ch[rt][i]) {
fail[ch[rt][i]]=rt;
Q.push(ch[rt][i]);
}
while (!Q.empty()) {
int x=Q.front(); Q.pop();
for (int i=0;i<26;i++) {
if (ch[x][i]) {
fail[ch[x][i]]=ch[fail[x]][i];
Q.push(ch[x][i]);
}
else ch[x][i]=ch[fail[x]][i];
}
}
for (int i=1;i<=tot;i++) {
son[fail[i]].push_back(i);
}
}
void dfs(int x) {
ent[x]=++tim;
for (int i=0;i<son[x].size();i++) dfs(son[x][i]);
lef[x]=tim;
}
void Add(int x,int del) {
while (x<N) bit[x]+=del,x+=x&-x;
}
int Query(int x) {
int ans=0;
while (x) ans+=bit[x],x-=x&-x;
return ans;
}
void Solve() {
int x=rt,now=0;
for (int i=1;i<=l;i++) {
if (s[i]=='B') Add(ent[x],-1),x=fa[x];
else if (s[i]=='P') {
now++;
for (int j=0;j<qy[now].size();j++) {
int r=qy[now][j].first;
int t=Query(lef[ord[r]])-Query(ent[ord[r]]-1);
ans[qy[now][j].second]=t;
}
}
else {
x=ch[x][s[i]-'a'];
Add(ent[x],1);
}
}
}
int main() {
scanf("%s",s+1);
l=strlen(s+1); insert();
GetFail(); dfs(rt);
scanf("%d",&m);
for (int i=1;i<=m;i++) {
int x,y; scanf("%d%d",&x,&y);
qy[y].push_back(make_pair(x,i));
}
Solve();
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}