题意：
题解：
我们观察一下它打字的过程，输入一个字符/回退一格，这不就是建立trie的过程吗？
根据题意我们可以建出一个trie，然后可以知道trie上哪个节点代表第几个打印的字符串。
那么考虑如何求答案，这是一个字符串匹配，而且还有trie，所以我们可以建立一个AC自动机。
如果有一个问题(x,y)，那么我们只需要在AC自动机（trie）从上往下沿着字符串y走，每走一步，就判断一下这个节点如果一直跳fail是不是能够到达x这个节点，如果是就答案加一。换句话说，每走一步，判断一下这个节点在fail树上是不是x的子节点即可。
那么我们先将问题离线了并建出fail树，然后将每个询问(x,y)挂到y所在的节点上去。接着遍历AC自动机（trie），每走一个节点就在树状数组上加一，遇到一个有询问的节点，就在树状数组上查询一下它的子树即可。
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; int n,m,df,num[100002],dfn[100002],zjds[100002],cnt,f[100002],ans[100002]; char s[100002]; typedef struct{ int fall,fa,nex[30]; }P; typedef struct{ int to,num; }PP; P p[100002]; vector<int>g[100002]; vector<PP>q[100002]; void trie(){ int l=strlen(s),now=0; for (int i=0;i<l;i++) if (s[i]=='P')num[++n]=now; else if (s[i]=='B')now=p[now].fa; else { if (!p[now].nex[s[i]-'a']) { p[now].nex[s[i]-'a']=++cnt; p[cnt].fa=now; } now=p[now].nex[s[i]-'a']; } } void bfs(){ queue<int>q; q.push(0); while(!q.empty()) { int u=q.front(),w;q.pop(); for (int i=0;i<26;i++) if (p[u].nex[i]) { if (!u){q.push(p[u].nex[i]);continue;} w=p[u].fall; while(w && !p[w].nex[i])w=p[w].fall; if (p[w].nex[i])p[p[u].nex[i]].fall=p[w].nex[i]; q.push(p[u].nex[i]); } } for (int i=1;i<=cnt;i++) g[p[i].fall].push_back(i); } void dfs(int x){ dfn[x]=++df;zjds[x]=1; for (int i=0;i<g[x].size();i++) { dfs(g[x][i]);zjds[x]+=zjds[g[x][i]]; } } void gengxin(int x,int y){ for (;x<=df;x+=x&-x) f[x]+=y; } int chaxun(int x){ int ans=0; for (;x>=1;x-=x&-x) ans+=f[x]; return ans; } void xunwen(){ int l=strlen(s),now=0;n=0; for (int i=0;i<l;i++) if (s[i]=='P') { n++; for (int j=0;j<q[n].size();j++) ans[q[n][j].num]=chaxun(dfn[num[q[n][j].to]]+zjds[num[q[n][j].to]]-1)-chaxun(dfn[num[q[n][j].to]]-1); } else if (s[i]=='B'){gengxin(dfn[now],-1);now=p[now].fa;} else {now=p[now].nex[s[i]-'a'];gengxin(dfn[now],1);} } int main() { scanf("%s",s); memset(p,0,sizeof(p)); trie(); scanf("%d",&m); for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); PP a;a.to=u;a.num=i; q[v].push_back(a); } bfs();dfs(0); xunwen(); for (int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }