测试地址：阿狸的打字机 做法：本题需要用到AC自动机+树状数组。 因为题目是一个多模式串的匹配问题，所以很快想到对所有输出的字符串建AC自动机。 根据AC自动机的性质，如果一个点能够通过 fail f a i l 指针走到另一个点，表示这个点代表的字符串的一个后缀等于走到的点代表的字符串。那么我们要知道串 Y Y 中有多少串XX，就是求在从根到代表串 Y Y 的点的路径上，有多少个点能通过failfail指针走到代表串 X X 的点。 又因为根据AC自动机建造的步骤，除了根每个点都有且仅有一个failfail指针指向已经BFS扩展过的点，所以所有 fail f a i l 指针一定连成一棵树。令 fail f a i l 指针指向的是父亲，那么上述“从根到代表串 Y Y 的点的路径上，有多少个点能通过failfail指针走到代表串 X X 的点”的询问，就可以变成询问“从根到代表串YY的点的路径上，有多少个点属于 fail f a i l 树中以代表串 X X 的点为根的子树”，这显然是在询问failfail树上的子树和。 我们把所有询问按 y y 从小到大排序，这样就有三个操作：在一个点上加一或减一，询问子树和。因为我们知道一棵子树在DFS序上是连续的，所以我们把failfail树的DFS序处理出来，然后单点修改区间求和显然可以用树状数组完成，这样就完成了此题。 以下是本人代码：
#include <bits/stdc++.h> using namespace std; int n=0,m,p[100010],ans[100010],st[100010],h,t,first[100010]={0}; int tot,pre[100010],ch[100010][26]={0},fail[100010],a[100010]={0}; int l[100010],r[100010],tim=0; char s[100010]; struct query { int id,x,y; }q[100010]; struct edge { int v,next; }e[100010]; bool cmp(query a,query b) { return a.y<b.y; } void insert(int a,int b) { e[++tot].v=b,e[tot].next=first[a],first[a]=tot; } void build() { tot=0; st[1]=h=t=1; while(h<=t) { int v=st[h++]; for(int i=0;i<26;i++) if (ch[v][i]) { int x=v; while(x!=1&&!ch[fail[x]][i]) x=fail[x]; if (v!=1&&ch[fail[x]][i]) fail[ch[v][i]]=ch[fail[x]][i]; else fail[ch[v][i]]=1; insert(fail[ch[v][i]],ch[v][i]); st[++t]=ch[v][i]; } } } void dfs(int v,int fa) { l[v]=++tim; for(int i=first[v];i;i=e[i].next) if (e[i].v!=fa) dfs(e[i].v,v); r[v]=tim; } int lowbit(int x) { return x&(-x); } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) a[i]+=c; } int sum(int x) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=a[i]; return ans; } int main() { scanf("%s",s); int x=1,len=strlen(s); pre[1]=0; tot=1; for(int i=0;i<len;i++) { if (s[i]=='P') p[++n]=x; else if (s[i]=='B') x=pre[x]; else { if (!ch[x][s[i]-'a']) { ch[x][s[i]-'a']=++tot; pre[tot]=x; } x=ch[x][s[i]-'a']; } } n=tot; build(); dfs(1,0); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].x,&q[i].y); q[i].id=i; } sort(q+1,q+m+1,cmp); x=1; int y=1,nowq=1; for(int i=0;i<len;i++) { if (s[i]=='P') { while(nowq<=m&&q[nowq].y==y) { ans[q[nowq].id]=sum(r[p[q[nowq].x]])-sum(l[p[q[nowq].x]]-1); nowq++; } y++; } else if (s[i]=='B') { add(l[x],-1); x=pre[x]; } else { x=ch[x][s[i]-'a']; add(l[x],1); } } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }