Description
令$s$与$w$为两字符串，下标从$0$开始，定义：
1.$w[l,r]$表示字符串$w$在区间$[l,r]$中的子串；
2.$w$在$s$中出现的频率定义为$w$在$s$中出现的次数；
3.$f(s,w,l,r)$表示$w[l,r]$在$s$中出现的频率。
比如$f(ababa,aba,0,2)=2$。
现在给定串$s$，$m$个区间$[l,r]$和长度$k$，你要回答$q$个询问，每个询问给你一个长度为$k$的字符串$w$和两个整数$a,b$，求：
$$sum_{i=a}^b f(s,w,l_i,r_i)$$
Solution
如果查询一个串在另一个串内的出现次数，可以建立模板串的SAM，所有后缀节点赋值为1，求文本串的子树和，可以DP预处理
$qk$为定值，分类讨论：
$k$较小时：
做法一：
离线询问，记录所有区间的出现次数，$O(k^2)$暴力做，时间复杂度$O(qk^{2.5})$
做法二：
记录所有区间的出现位置，对于每个询问二分求出有多少个区间$[L,R]$在$[a,b]$中，时间复杂度$O(qk^2log m )$
$q$较小时
对于每个询问串，求出每个后缀最多匹配的长度和在SAM上匹配到的位置，计算答案时在parent树上倍增跳到合适的位置
时间复杂度$O(qmlog n)$
平衡两个时间复杂度后，发现两种方案时间复杂度非常相近，于是都可做
#include<algorithm> #include<iostream> #include<cstdio> using namespace std; int n,m,q,K,las=1,tot=1,buc[100005],sa[200005],siz[200005]; char s[100005]; struct Node{ int l,r; }node[100005]; struct SAM{ int len,fa,ch[27]; }sam[200005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } namespace task1{ int B=20,L=1,R=0; long long ans[100005],vis[325][325]; struct Que{ int a,b,id; char str[325]; bool operator <(const Que &z)const{return a/B==z.a/B?b<z.b:a<z.a;} }que[100005]; void add(int x){++vis[node[x].l][node[x].r];} void del(int x){--vis[node[x].l][node[x].r];} long long calc(int x){ long long ret=0; for(int i=1;i<=K;i++){ int p=1; for(int j=i;j<=K;j++){ int c=que[x].str[j]-'a'; if(!sam[p].ch[c])break; p=sam[p].ch[c],ret+=1ll*vis[i][j]*siz[p]; } } return ret; } void main(){ for(int i=1;i<=q;i++)scanf("%s",que[i].str+1),que[i].a=read()+1,que[i].b=read()+1,que[i].id=i; sort(que+1,que+q+1); for(int i=1;i<=q;i++){ while(L<que[i].a)del(L++); while(L>que[i].a)add(--L); while(R<que[i].b)add(++R); while(R>que[i].b)del(R--); ans[que[i].id]=calc(i); } for(int i=1;i<=q;i++)printf("%lld ",ans[i]); } } namespace task2{ int f[200005][21],pos[100005],len[100005]; long long ans; char str[100005]; long long find(int x,int v){ for(int i=20;~i;i--)if(f[x][i]&&sam[f[x][i]].len>=v)x=f[x][i]; return siz[x]; } void main(){ for(int i=1;i<=tot;i++)f[i][0]=sam[i].fa; for(int i=1;i<=20;i++)for(int j=1;j<=tot;j++)f[j][i]=f[f[j][i-1]][i-1]; for(int i=1;i<=q;i++){ scanf("%s",str+1),ans=0; int p=1,l=0; for(int j=1;j<=K;j++){ int c=str[j]-'a'; if(sam[p].ch[c])++l,p=sam[p].ch[c]; else{ while(p>1&&!sam[p].ch[c])p=sam[p].fa; if(sam[p].ch[c])l=sam[p].len+1,p=sam[p].ch[c]; else l=0; } pos[j]=p,len[j]=l; } int a=read()+1,b=read()+1; for(int j=a;j<=b;j++)if(len[node[j].r]>=node[j].r-node[j].l+1)ans+=find(pos[node[j].r],node[j].r-node[j].l+1); printf("%lld ",ans); } } } void insert(int c){ int p=las,np=las=++tot; sam[np].len=sam[p].len+1; for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np; if(!p)sam[np].fa=1; else{ int q=sam[p].ch[c]; if(sam[q].len==sam[p].len+1)sam[np].fa=q; else{ int nq=++tot; sam[nq]=sam[q],sam[nq].len=sam[p].len+1,sam[q].fa=sam[np].fa=nq; for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq; } } siz[np]=1; } int main(){ n=read(),m=read(),q=read(),K=read(),scanf("%s",s+1); for(int i=1;i<=n;i++)insert(s[i]-'a'); for(int i=1;i<=tot;i++)++buc[sam[i].len]; for(int i=1;i<=n;i++)buc[i]+=buc[i-1]; for(int i=tot;i;i--)sa[buc[sam[i].len]--]=i; for(int i=tot;i;i--)siz[sam[sa[i]].fa]+=siz[sa[i]]; for(int i=1;i<=m;i++)node[i]=(Node){read()+1,read()+1}; if(K<320)task1::main(); else task2::main(); return 0; }