询问x串在y串中出现次数，就是有多少y串的节点能顺着fail边跑到x的终止节点。所以建出fail树，求end[x] 为根的子树中有多少y的节点。 这个可以离线询问，用树状数组维护。
#include<queue> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define maxn 200005 using namespace std; void read(int &a) { a=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9') { a*=10;a+=c-'0'; c=getchar(); } } int c[maxn]; int N; int low(int x) {return (x&(-x));} void add(int x,int d) { while(x<=N) { c[x]+=d; x+=low(x); } } int ask(int x) { int ans=0; while(x>=1) { ans+=c[x]; x-=low(x); } return ans; } struct QUE{int x,y,id;}q[maxn]; bool cmp(QUE A,QUE B) {return A.y<B.y;} int ANS[maxn]; char s[maxn]; int T,fa[maxn]; struct E{int to,nxt;}b[maxn<<1]; int id[maxn],fst[maxn],tot; void ins(int f,int t) { b[++tot]=(E){t,fst[f]};fst[f]=tot; b[++tot]=(E){f,fst[t]};fst[t]=tot; } int dfn[maxn],dfs_c; int in[maxn],out[maxn]; void dfs(int x) { dfn[++dfs_c]=x; in[x]=dfs_c; for(int i=fst[x];i;i=b[i].nxt) { int v=b[i].to; if(!in[v]) dfs(v); } out[x]=dfs_c; } struct Trie { int val[maxn]; int ch[maxn][30],cnt; int lst[maxn],fail[maxn]; void insert() { int p=0; int n=strlen(s+1); for(int i=1;i<=n;i++) { if(s[i]>='a'&&s[i]<='z') { int c=s[i]-'a'+1; if(!ch[p][c]) { ch[p][c]=++cnt; fa[ch[p][c]]=p; } p=ch[p][c]; } else if(s[i]=='B')p=fa[p]; else id[++T]=p; } } queue<int> Q; void build() { for(int i=1;i<=26;i++) if(ch[0][i]) { Q.push(ch[0][i]); ins(0,ch[0][i]); } while(!Q.empty()) { int r=Q.front();Q.pop(); for(int i=1;i<=26;i++) { int u=ch[r][i]; if(!u) { ch[r][i]=ch[fail[r]][i]; continue; } Q.push(u); int p=fail[r]; while(p&&!ch[p][i]) p=fail[p]; fail[u]=ch[p][i]; ins(ch[p][i],u); } } } void work() { int p=0,H=1,t=0; int n=strlen(s+1); for(int i=1;i<=n;i++) { if(s[i]>='a'&&s[i]<='z') { p=ch[p][s[i]-'a'+1]; add(in[p],1); } else if(s[i]=='B') { add(in[p],-1); p=fa[p]; } else { t++; while(q[H].y==t) { int x=id[q[H].x]; ANS[q[H].id]=ask(out[x])-ask(in[x]-1); H++; } } } } }AC; int main() { scanf("%s",s+1); AC.insert();AC.build(); int m;scanf("%d",&m); for(int i=1;i<=m;i++) { read(q[i].x); read(q[i].y); q[i].id=i; } dfs(0);N=dfs_c; sort(q+1,q+m+1,cmp); AC.work(); for(int i=1;i<=m;i++) printf("%d\n",ANS[i]); return 0; }