题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2434
dfs AC自动机，走过的点权值+1，回溯的时候权值-1；走到询问的 y 串的节点，看一下此时 x 串 fail 树子树和即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } const int N=1e5+5,K=26; int n,m,tot=1,dy[N],c[N][K],tc[N][K],fa[N],fl[N]; int hd[N],xnt,to[N<<1],nxt[N<<1],dfn[N],ot[N],tim; int h2[N],t2[N],nt2[N],ans[N]; int q[N],f[N]; char s[N]; void add(int x,int y) {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;fl[y]=x;} void get_fl() { int he=0,tl=0; for(int i=0,v;i<26;i++) if((v=c[1][i]))q[++tl]=v,add(1,v),tc[1][i]=v; else tc[1][i]=1; while(he<tl) { int k=q[++he],pr=fl[k]; for(int i=0,v;i<26;i++) if((v=c[k][i])) q[++tl]=v,add(tc[pr][i],v),tc[k][i]=v; else tc[k][i]=tc[pr][i]; } } void ini_dfs(int cr) { dfn[cr]=++tim; for(int i=hd[cr];i;i=nxt[i]) ini_dfs(to[i]); ot[cr]=tim; } void Inc(int x,int k){for(;x<=tot;x+=(x&-x))f[x]+=k;} int qry(int x){int ret=0;for(;x;x-=(x&-x))ret+=f[x];return ret;} void dfs(int cr) { Inc(dfn[cr],1); for(int i=h2[cr];i;i=nt2[i]) ans[i]=qry(ot[t2[i]])-qry(dfn[t2[i]]-1); for(int i=0;i<26;i++) if(c[cr][i])dfs(c[cr][i]); Inc(dfn[cr],-1); } int main() { scanf("%s",s+1); n=strlen(s+1); int cr=1,cnt=0; for(int i=1;i<=n;i++) { if(s[i]>='a') { c[cr][s[i]-'a']=++tot; fa[tot]=cr; cr=tot; } else if(s[i]=='B')cr=fa[cr]; else dy[++cnt]=cr; } get_fl(); ini_dfs(1); m=rdn(); for(int i=1;i<=m;i++) { int u=rdn(),v=rdn(); u=dy[u]; v=dy[v]; t2[i]=u;nt2[i]=h2[v];h2[v]=i; } dfs(1); for(int i=1;i<=m;i++)printf("%d ",ans[i]); return 0; }