给定\(N(N\leq 10^5)\)个串，\(m(m\leq 10^5)\)次询问，每次询问第\(x\)个串在第\(y\)个串中出现了几次。
Solution脑抽又调了一个小时。。。
考虑AC自动机fail指针的含义，如果 \(fail[x]=y\) 那说明以 \(y\) 结尾的串在 \(x\) 中出现了。
于是询问 \(x\) 在 \(y\) 中出现了几次实际上就是问trie树上根到 \(y\) 的路径有多少点的 \(fail\) 指针直接或间接指向了 \(x\) 的结尾节点。可以把 \(fail\) 指针当做树边拎出来建树。
于是询问变成在新的 \(fail\) 树上以点 \(x\) 为根的子树中有多少点是在trie树上根到 \(y\) 的路径上的。
先dfs一遍 \(fail\) 树求出dfs序转化为序列上的问题。
直接在 \(fail\) 树上做貌似不是很好做，我们回到原来的trie树上，dfs 一遍整个trie树。进入一个点就在序列上对应位置+1，退出一个点就在对应位置-1，这样保证了只有当前路径是有值的。如果碰到了单词节点，就相当于我们遇到了询问 \((x,y)\) 中的 \(y\)，扫一下所有的 \(x\)，查子树和就行了。
Code #include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; const int M=8e5+5; const int N=1e5+5; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) vector< pii > v[N]; vector<int> js[M];char a[N]; int tot,head[M],ch[M][27],ans[N],fa[M]; int n,m,cnt,fs[N],fail[M],dfn[M],f[M],sze[M]; struct Edge{ int to,nxt; }edge[M]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } void add(int x){ while(x) f[x]++,x-=x&-x; } void clr(int x){ while(x) f[x]--,x-=x&-x; } int query(int x){ int now=0; while(x<=tot) now+=f[x],x+=x&-x; return now; } int getint(){ int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } void getfail(){ std::queue<int> q; for(int i=0;i<26;i++) if(ch[0][i]) q.push(ch[0][i]); while(q.size()){ int u=q.front();q.pop();add(fail[u],u); for(int i=0;i<26;i++){ if(ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]); else ch[u][i]=ch[fail[u]][i]; } } } void dfs(int now){ sze[now]=1;dfn[now]=++tot; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; dfs(to);sze[now]+=sze[to]; } } void sdfs(int now){ add(dfn[now]); for(int x:js[now]) for(auto y:v[x]) ans[y.second]=query(dfn[fs[y.first]])-query(dfn[fs[y.first]]+sze[fs[y.first]]); for(int i=0;i<26;i++) if(ch[now][i]) sdfs(ch[now][i]); clr(dfn[now]); } signed main(){ scanf("%s",a+1); int len=strlen(a+1),now=0; for(int i=1;i<=len;i++){ if(a[i]>='a' and a[i]<='z'){ if(!ch[now][a[i]-'a']) ch[now][a[i]-'a']=++tot,fa[tot]=now; now=ch[now][a[i]-'a']; } else if(a[i]=='B') now=fa[now]; else n++,js[now].pb(n),fs[n]=now; } tot=0;getfail();dfs(0);int cnts=0; memset(ch,0,sizeof ch);now=0; for(int i=1;i<=len;i++){ if(a[i]>='a' and a[i]<='z'){ if(!ch[now][a[i]-'a']) ch[now][a[i]-'a']=++cnts; now=ch[now][a[i]-'a']; } else if(a[i]=='B') now=fa[now]; } m=getint(); for(int i=1;i<=m;i++){ int x=getint(),y=getint(); v[y].pb(mp(x,i)); } sdfs(0); for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }