为了方便，用$N=10^{5}$来描述复杂度

（对原串建立SAM）注意到$\sum|w|=qk\le N$，考虑对$q$和$k$的大小关系分类讨论：

1.若$q\le k$，即询问次数较少，将其与原串建立一个广义SAM，然后找到枚举所有区间，倍增找到该区间对应子串的位置，该right集合大小即为答案，时间复杂度为$o(qN\log N)$

（建立广义SAM的实际操作，由于只关心于$s$的子串，并不需要新建节点，会更方便一些）

2.若$k<q$，即串长较短，直接暴力枚举查询串的所有子串，并在原串的SAM上查询其出现次数（即对应节点的right集合大小），然后统计其在$[l_{a},r_{a}],[l_{a+1},r_{a+1}],…,[l_{b},r_{b}]$中出现了几次：

将$m$个区间中相同区间存储位置到同一个vector中，然后即查询该区间对应的vector有几个元素在$[a,b]$中，通过二分即可，时间复杂度为$o(qk^{2}\log N)=o(Nk\log N)$

显然总复杂度为$O(N\sqrt{N}\log N)$，可以通过

1 #include
2 using namespace std;
3 #define N 200005
4 #define ll long long
5 vectorv[N];
6 int V,n,m,q,l,lst,a,b,nex[N],len[N],R[N],ch[N][26],A[N],B[N],pos[N],Len[N],fa[N][20];
7 ll ans;
8 char s[N],ss[N];
9 void add(int c){
10 int p=lst,np=lst=++V;
11 len[np]=len[p]+1;
12 while ((p)&&(!ch[p][c])){
13 ch[p][c]=np;
14 p=nex[p];
15 }
16 if (!p)nex[np]=1;
17 else{
18 int q=ch[p][c];
19 if (len[q]==len[p]+1)nex[np]=q;
20 else{
21 int nq=++V;
22 nex[nq]=nex[q];
23 nex[q]=nex[np]=nq;
24 len[nq]=len[p]+1;
25 memcpy(ch[nq],ch[q],sizeof(ch[q]));
26 while ((p)&&(ch[p][c]==q)){
27 ch[p][c]=nq;
28 p=nex[p];
29 }
30 }
31 }
32 }
33 void dfs(int k,int f){
34 fa[k][0]=f;
35 for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1]; 36 for(int i=0;i=0;i--)
43 if (len[fa[k][i]]>=l)k=fa[k][i];
44 return k;
45 }
46 int main(){
47 scanf("%d%d%d%d%s",&n,&m,&q,&l,s);
48 for(int i=0;i1)&&(!ch[k][ss[i]-'a']))k=nex[k];
62 Len[i]=len[k];
63 if (i)Len[i]=min(Len[i],Len[i-1]);
64 if (ch[k][ss[i]-'a']){
65 k=ch[k][ss[i]-'a'];
66 Len[i]++;
67 }
68 pos[i]=k;
69 }
70 for(int j=a;j<=b;j++) 71 if (Len[B[j]]>=B[j]-A[j]+1)ans+=R[get(pos[B[j]],B[j]-A[j]+1)];
72 printf("%lld\n",ans);
73 }
74 }
75 else{
76 for(int i=0;i<l*l;i++)v[i].clear();
77 for(int i=0;i<m;i++)v[A[i]*l+B[i]].push_back(i);
78 for(int ii=1;ii<=q;ii++){
79 scanf("%s%d%d",ss,&a,&b);
80 ans=0;
81 for(int i=0;i<l;i++)
82 for(int j=i,k=1;j<l;j++){
83 k=ch[k][ss[j]-'a'];
84 if (!k)break;
85 int p=i*l+j;
86 int posl=lower_bound(v[p].begin(),v[p].end(),a)-v[p].begin();
87 int posr=upper_bound(v[p].begin(),v[p].end(),b)-v[p].begin()-1;
88 ans+=(ll)R[k]*max(posr-posl+1,0);
89 }
90 printf("%lld\n",ans);
91 }
92 }
93 return 0;
94 }