令 $ s $ 与 $ w $ 为两字符串，定义：
1. $ w[l, r] $ 表示字符串 $ w $ 在区间 $ [l, r] $ 中的子串；
2. $ w $ 在 $ s $ 中出现的频率定义为$ w $ 在 $ s $ 中出现的次数；
3. $ f(s, w, l, r) $ 表示 $ w[l, r] $ 在 $ s $ 中出现的频率。
比如 $ f( exttt{ababa}, exttt{aba}, 1, 3) = 2 $。
现在给定串 $ s $，$ m $ 个区间 $ [l, r] $ 和长度 $ k $，你要回答 $ q $ 个询问，每个询问给你一个长度为 $ k $ 的字符串 $ w $ 和两个整数 $ a, b $，求：
$$ sumlimits_{i = a} ^ b f(s, w, l_i, r_i) $$
Sol
对S串建出sam，预处理每个节点right集合大小。
注意到Q*k=1e5 考虑分类讨论：、
1.Q>k
枚举Q，枚举w的每一个子串[l,r]，二分出询问[l,r]中有多少个在[a,b]中，乘上right大小即可。
效率O(q*k^2*log)=O(wsqrt(w)log)
2.Q<k
枚举Q，枚举w的每一位，记录在sam上匹配到了哪个点，匹配长度是多少。
然后枚举a到b的每一个区间[l,r]，先走到r，然后倍增到l，加上right即可
效率O(Q(k+m))
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #define maxn 400005 using namespace std; int n,li,len,ls,cnt,ans[maxn],tr[maxn][94],fail[maxn],head[maxn],tot; int dfn[maxn],ed[maxn],sc,c[maxn]; char ch[maxn],s[maxn]; struct no{ int v,nex; }e[maxn]; void add(int t1,int t2){ e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot; } struct bit{ int tr[maxn]; void add(int i,int v){ for(;i<=cnt;i+=i&-i)tr[i]+=v; } int ask(int i){ int sum=0;for(;i;i-=i&-i)sum+=tr[i];return sum; } }T; struct node{int p,id;}; vector<node>q[maxn]; vector<int>G[maxn]; void ins(int l,int id){ for(int i=1;i<=l;i++)ch[i]-=33; int k=0; for(int i=1;i<=l;i++){ if(!tr[k][ch[i]])tr[k][ch[i]]=++cnt; k=tr[k][ch[i]]; } k=0; for(int i=l;i>0;i--){ if(!tr[k][ch[i]])tr[k][ch[i]]=++cnt; k=tr[k][ch[i]];ed[i]=k; } k=0; q[0].push_back((node){ed[li+1],id}); cout<<ed[2]<<' '<<ed[li+1]<<' '<<id<<endl; for(int i=1;i+li<=l;i++){ k=tr[k][ch[i]]; if(i+li==l)q[k].push_back((node){-1,id}); else q[k].push_back(node{ed[i+li+1],id}); } } void build(){ queue<int>q; for(int i=0;i<94;i++)if(tr[0][i])q.push(tr[0][i]); while(!q.empty()){ int k=q.front();q.pop(); add(fail[k],k); for(int i=0;i<94;i++){ if(tr[k][i])fail[tr[k][i]]=tr[fail[k]][i],q.push(tr[k][i]); else tr[k][i]=tr[fail[k]][i]; } } } void dfs(int k){ dfn[k]=++sc; for(int i=head[k];i;i=e[i].nex)dfs(e[i].v); ed[k]=sc; } void solve(int k){ for(int i=head[k];i;i=e[i].nex)solve(e[i].v); for(int i=0;i<G[k].size();i++){ T.add(G[k][i],1); } for(int i=0;i<q[k].size();i++){ node t=q[k][i]; if(t.id==1)cout<<k<<' '<<t.p<<' '<<G[k].size()<<endl; if(t.p==-1)ans[t.id]+=T.ask(ed[0]); else ans[t.id]+=T.ask(ed[t.p])-T.ask(dfn[t.p]-1); } for(int i=0;i<G[k].size();i++)T.add(G[k][i],-1); } int main(){ cin>>li;scanf(" %s",s+1);n=strlen(s+1); for(int i=1;i<=n;i++)s[i]-=33; cin>>n; for(int i=1;i<=n;i++){ scanf("%s",ch+1); int l=strlen(ch+1); if(l<=li)ans[i]=n-l+1; else ins(l,i); } build();dfs(0); cout<<"haha "<<tr[0]['z'-33]<<endl; int k=0;c[n+1]=dfn[0]; for(int i=n;i>=1;i--){ k=tr[k][s[i]];c[i]=k; } k=0;G[0].push_back(li); for(int i=1;i+li<=n;i++){ k=tr[k][s[i]]; cout<<k<<' '<<fail[k]<<' '<<c[i+li+1]<<endl; G[k].push_back(c[i+li+1]); } solve(0); for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }