首先先对\(s\)建一个\(\operatorname{SAM}\)，设\(w=kq\)

发现\(k,q\leq 10^5\)，但是\(w\leq 10^5\)，于是套路地根号讨论一下

如果\(k\leq \sqrt{w}\)，那么说明单个询问串都很短，我们完全可以暴力长度为\(k\)的字符串的所有子串，之后二分查询一下这个子串在\([a,b]\)的询问里出现的次数，这个子串在\(s\)出现的次数直接边走边查就好了，这边的复杂度是\(O(qk^2\log m)=O(w\sqrt{w}\log m)\)

如果\(k>\sqrt{w}\)，那么说明单个询问串很长，但是询问个数\(q\leq \sqrt{w}\)，于是我们直接扫\([a,b]\)范围内的所有区间，考虑到子串\([l,r]\)在\(s\)中出现了多少次可以转化为\(s\)有多少个前缀和前缀\(r\)的\(\operatorname{LCS}\)长度不小于\(r-l+1\)，于是直接树上倍增求解，复杂度\(O(qm\log n)=O(m\sqrt{w}\log n)\)

代码

#include
    
     #define re register#define LL long longinline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=2e5+5;int fa[maxn],A[maxn],tax[maxn],son[maxn][26],len[maxn],sz[maxn];int n,m,k,q,lst,cnt;char S[maxn>>1];inline void ins(int c) {    int p=++cnt,f=lst;lst=p;    len[p]=len[f]+1,sz[p]=1;    while(f&&!son[f][c]) son[f][c]=p,f=fa[f];    if(!f) {fa[p]=1;return;}    int x=son[f][c];    if(len[f]+1==len[x]) {fa[p]=x;return;}    int y=++cnt;    len[y]=len[f]+1,fa[y]=fa[x],fa[p]=fa[x]=y;    for(re int i=0;i<26;i++) son[y][i]=son[x][i];    while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];}namespace sub1 {    int id[350][350],tot;    std::vector
     
       v[maxn>>1];    inline int find(int t,int x) {        int l=0,r=v[t].size()-1,h=-1;        while(l<=r) {            int mid=l+r>>1;            if(v[t][mid]<=x) h=mid,l=mid+1;                else r=mid-1;        }        return h+1;    }    void solve() {        for(re int i=1;i<=k;++i)            for(re int j=i;j<=k;++j) id[i][j]=++tot;         for(re int x,y,i=1;i<=m;i++) {            x=read()+1,y=read()+1;            v[id[x][y]].push_back(i);        }        for(re int x,y,i=1;i<=q;i++) {            scanf("%s",S+1);x=read(),y=read()+1;            LL ans=0;            for(re int now=1,j=1;j<=k;++j,now=1)                 for(re int p=j;p<=k;++p) {                    now=son[now][S[p]-'a'];                    if(!now) break;                    ans+=1ll*sz[now]*(find(id[j][p],y)-find(id[j][p],x));                }            printf("%lld\n",ans);        }    }}namespace sub2 {    int ql[maxn>>1],qr[maxn>>1],deep[maxn];    int lg[maxn>>1],pos[maxn>>1],ml[maxn>>1],f[18][maxn];    void solve() {        for(re int i=1;i<=m;i++) ql[i]=read()+1,qr[i]=read()+1;        deep[1]=1;for(re int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;        for(re int i=2;i<=cnt;i++) deep[A[i]]=deep[fa[A[i]]]+1;        for(re int i=1;i<=cnt;i++) {            int x=A[i];f[0][x]=fa[x];            for(re int j=1;j<=lg[deep[x]];++j)                f[j][x]=f[j-1][f[j-1][x]];        }        int x,y;        while(q--) {            scanf("%s",S+1);x=read()+1,y=read()+1;            int now=1,l=0;LL ans=0;            for(re int i=1;i<=k;i++) {                if(son[now][S[i]-'a']) {                    pos[i]=now=son[now][S[i]-'a'];                    ml[i]=++l;continue;                }                while(now&&!son[now][S[i]-'a']) now=fa[now];                if(!now) pos[i]=now=1,ml[i]=l=0;                 else ml[i]=l=len[now]+1,pos[i]=now=son[now][S[i]-'a'];            }            for(re int i=x;i<=y;++i) {                if(ml[qr[i]]
      
       =0;--j)                    if(len[f[j][now]]>=qr[i]-ql[i]+1) now=f[j][now];                ans+=sz[now];            }            printf("%lld\n",ans);        }    }}int main() {    n=read(),m=read(),q=read(),k=read();    scanf("%s",S+1);lst=cnt=1;    for(re int i=1;i<=n;i++) ins(S[i]-'a');    for(re int i=1;i<=cnt;i++) tax[len[i]]++;    for(re int i=1;i<=n;i++) tax[i]+=tax[i-1];    for(re int i=1;i<=cnt;i++) A[tax[len[i]]--]=i;    for(re int i=cnt;i;--i) sz[fa[A[i]]]+=sz[A[i]];    if(k<=std::sqrt(k*q)) sub1::solve();else sub2::solve();    return 0;}