离线处理所有询问。
对于$r-l\leq 50$的情况：
按照串长从$1$到$51$分别把所有子串按照第一位字符为第一关键字，上一次排序结果为第二关键字进行$O(n)$基数排序。
同理也可以用上一次比较结果来判断这一次某两个子串是否相同。
对于每个询问，找到排序结果中对应的区间，在里面二分出起点$x$，问题转化为从$x$开始贪心会一直往右跳最终能跳过多少个位置。
继续离线，预处理出每个$x$的后继$f_x$作为$x$的祖先，DFS这棵树的时候在栈上二分即可。
时间复杂度$O(len\times n+m\log n)$。
对于$r-l\geq 51$的情况：
因为串比较长而且随机，所以匹配次数不会很多，暴力找到所有匹配位置即可。
先在后缀数组上找到对应的区间$[l,r]$，问题转化为在$[l,r]$中找到值比$k$大的最小的值。
设$T_k$表示仅保留所有$\geq k$的值的线段树，在$T_k$中查询区间最小值即可。而$T$可以通过可持久化在$O(n\log n)$的时间内预处理出来。
设$cnt$为匹配次数，则时间复杂度为$O(cnt\log n)$。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=400010,S=256;
int n,m,mx,now,i,j,x,y,len,val[N],e[N][4];ll ans[N];
char a[N],b[N];
vector<int>que[N],need[N];
int c[N],q[N],id[N],nq[N],nid[N],en[N],g[N],nxt[N];
int pool[N],top;ll sum[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void small(int o){
int S=e[o][0],T=e[o][1],p=id[e[o][2]+n];
int l=p,r=en[p],mid,t;
while(l<=r){
mid=(l+r)>>1;
if(q[mid]>=S)r=(t=mid)-1;else l=mid+1;
}
if(q[t]+len-1>T)return;
need[q[t]].push_back(o);
}
inline void add(int x,int y){nxt[x]=g[y];g[y]=x;}
inline void query(int o){
int T=e[o][1],l=1,r=top,mid,t=0;
while(l<=r){
mid=(l+r)>>1;
if(pool[mid]+len-1>T)l=(t=mid)+1;else r=mid-1;
}
ans[o]=sum[top]-sum[t];
}
void dfs(int x){
if(x){
pool[++top]=x;
sum[top]=sum[top-1]+val[x];
for(int i=0;i<need[x].size();i++)query(need[x][i]);
}
for(int i=g[x];i;i=nxt[i])dfs(i);
if(x)top--;
}
namespace SA{
const int M=2400000;
int n,rk[N],sa[N],height[N],tmp[N],cnt[N];char s[N];
int Log[N],f[18][200010];
int l[M],r[M],v[M],tot,root[N],fin;
void suffixarray(int n,int m){
int i,j,k;n++;
for(i=0;i<n;i++)cnt[rk[i]=s[i]]++;
for(i=1;i<m;i++)cnt[i]+=cnt[i-1];
for(i=0;i<n;i++)sa[--cnt[rk[i]]]=i;
for(k=1;k<=n;k<<=1){
for(i=0;i<n;i++){
j=sa[i]-k;
if(j<0)j+=n;
tmp[cnt[rk[j]]++]=j;
}
sa[tmp[cnt[0]=0]]=j=0;
for(i=1;i<n;i++){
if(rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k])cnt[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int));
memcpy(sa,tmp,n*sizeof(int));
if(j>=n-1)break;
}
for(j=rk[height[i=k=0]=0];i<n-1;i++,k++)
while(~k&&s[i]!=s[sa[j-1]+k])height[j]=k--,j=rk[sa[j]+1];
}
inline int lcp(int x,int y){
if(x>y)swap(x,y);
x++;
int k=Log[y-x+1];
return min(f[k][x],f[k][y-(1<<k)+1]);
}
int build(int a,int b){
int x=++tot;
v[x]=N;
if(a==b)return x;
int mid=(a+b)>>1;
l[x]=build(a,mid);
r[x]=build(mid+1,b);
return x;
}
int ins(int x,int a,int b,int c,int p){
int y=++tot;
v[y]=min(v[x],p);
if(a==b)return y;
int mid=(a+b)>>1;
if(c<=mid)l[y]=ins(l[x],a,mid,c,p),r[y]=r[x];
else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,p);
return y;
}
void ask(int x,int a,int b,int c,int d){
if(v[x]>=fin)return;
if(c<=a&&b<=d){fin=v[x];return;}
int mid=(a+b)>>1;
if(c<=mid)ask(l[x],a,mid,c,d);
if(d>mid)ask(r[x],mid+1,b,c,d);
}
void init(){
suffixarray(n,S);
for(i=1;i<=n;i++)f[0][i]=height[i];
for(i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
for(j=1;j<18;j++)for(i=1;i+(1<<j)-1<=n;i++)f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
int m=n>>1;
root[m]=build(1,n);
for(i=m-1;~i;i--)root[i]=ins(root[i+1],1,n,rk[i],i);
}
inline void solve(int o){
int S=e[o][0]-1,T=e[o][1]-1,p=rk[e[o][2]+(n>>1)-1];
int L=p,R=p,l,r,mid;
l=1,r=p-1;
while(l<=r){
mid=(l+r)>>1;
if(lcp(mid,p)>=len)r=(L=mid)-1;else l=mid+1;
}
l=p+1,r=n;
while(l<=r){
mid=(l+r)>>1;
if(lcp(mid,p)>=len)l=(R=mid)+1;else r=mid-1;
}
ll ret=0;
while(S+len-1<=T){
fin=N;
ask(root[S],1,n,L,R);
if(fin+len-1>T)break;
ret+=val[fin+1];
S=fin+len;
}
ans[o]=ret;
}
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++)val[i]=m-i;
scanf("%s%s",a+1,b+1);
for(i=1;i<=n;i++)a[i+n]=b[i];
read(m);
for(i=1;i<=m;i++){
int s,t,l,r;
read(s),read(t),read(l),read(r);
e[i][0]=s,e[i][1]=t,e[i][2]=l,e[i][3]=r;
que[r-l+1].push_back(i);
mx=max(mx,r-l+1);
}
for(i=1;i<=n+n;i++)SA::s[i-1]=a[i];
SA::n=n+n;
SA::init();
for(i=1;i<=n+n+1;i++)q[i]=i;
for(len=1;len<=mx;len++)if(len<=51){
for(i=0;i<S;i++)c[i]=0;
now=n+n-len+1;
for(i=1;i<=now;i++)c[a[i]]++;
for(i=1;i<S;i++)c[i]+=c[i-1];
for(i=now+1;i;i--){
x=q[i]-1;
if(!x)continue;
nq[c[a[x]]--]=x;
}
for(i=0;i<=now;i++)g[i]=0,need[i].clear();
for(i=1;i<=now;i=j){
for(j=i;j<=now;j++){
if(a[nq[i]]!=a[nq[j]])break;
if(id[nq[i]+1]!=id[nq[j]+1])break;
}
en[i]=j-1;
for(x=i;x<j;x++)nid[nq[x]]=i;
for(x=y=i;x<j;x++){
while(y<j&&nq[y]-nq[x]<len)y++;
add(nq[x],y<j?nq[y]:0);
}
}
for(i=1;i<=now;i++)q[i]=nq[i],id[i]=nid[i];
for(i=0;i<que[len].size();i++)small(que[len][i]);
dfs(0);
}else for(i=0;i<que[len].size();i++)SA::solve(que[len][i]);
for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}