Description
给定长度为n的字符串，m次询问，每次询问s[a...b]的所有子串与s[c...d]的LCP的最大值。n,m<=10^5。
Solution
感觉这种n,m<=10^5的题往大了说就几种做法。
一是O(nlogn)或O(n)预处理然后在线O(logn)单次回答询问（或许log带个指数？），常见的就是各种数据结构，倍增和二分。
二是离线之后各种暴搞，最常见的莫队就是O(nsqrtn)的。
然后回头看这题就是O(nlogn)预处理然后在线O(log^2n)回答询问
先把height数组求出来ST表建好喽
求最大值不好求，可以二分一个mid，答案就变成在[a,b-mid+1]中是否存在一个k，满足LCP(rk[k],rk[c])>=mid
观察到这个rk[k]一定是一段区间，那我们可以二分求出来这个区间的左端点和右端点[ansl,ansr]
然后主席树判一下[a,b-mid+1]中有没有点的rk是落在[ansl,ansr]这个区间里面就好啦
总复杂度O(nlog^2n)
Code
namespace NewweN{
const int N=1e5+5;
const int K=N*20;
int n,m,q,num,tot,height[N];
int root[N],sum[K],ch[K][2];
char s[N];int x[N],y[N],c[N];
int sa[N],rk[N],st[N][20],lg[N];
char buf[1048578];int ptr,MX;
char nc(){
if(ptr==MX) MX=fread(buf,1,1<<20,stdin),ptr=0;
return ptr==MX?EOF:buf[ptr++];
}
// #define getchar nc
int getint(){
int X=0,w=0;char ch=getchar();
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
void getsa(){
m=150;
for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[i]]--]=i;
for(int k=1;num=0,k<=n;k<<=1){
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);x[sa[1]]=num=1;
for(int i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] and y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==n) return;m=num;
}
}
void getheight(int k=0){
for(int i=1;i<=n;i++) rk[sa[i]]=i;
for(int i=1;i<=n;i++){
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(i+k<=n and j+k<=n and s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
}
void getst(){
lg[1]=0;
for(int i=2;i<=n;i++)
lg[i]=lg[i-1]+((1<<lg[i-1]+1)==i);
for(int i=1;i<=n;i++) st[i][0]=height[i];
for(int k=1;k<=lg[n];k++)
for(int i=1;i+(1<<k)-1<=n;i++)
st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]);
}
int query(int x,int y){
if(x==y) return n+1;
if(x>y) swap(x,y);x++;
int k=lg[y-x+1];
return min(st[x][k],st[y-(1<<k)+1][k]);
}
int modify(int pre,int l,int r,int c){
int cur=++tot;
sum[cur]=sum[pre]+1;ch[cur][0]=ch[pre][0];ch[cur][1]=ch[pre][1];
if(l==r) return cur;
int mid=l+r>>1;
c<=mid?ch[cur][0]=modify(ch[pre][0],l,mid,c):ch[cur][1]=modify(ch[pre][1],mid+1,r,c);
return cur;
}
int query(int cur,int pre,int l,int r,int ql,int qr){
if(sum[cur]-sum[pre]==0) return 0;
if(ql<=l and r<=qr) return 1;
int mid=l+r>>1,ans=0;
if(ql<=mid) ans|=query(ch[cur][0],ch[pre][0],l,mid,ql,qr);
if(mid<qr) ans|=query(ch[cur][1],ch[pre][1],mid+1,r,ql,qr);
return ans;
}
bool check(int a,int b,int c,int d,int x){
int l=1,r=rk[c],ansl=0,ansr=0;
while(l<=r){
int mid=l+r>>1;
if(query(mid,rk[c])>=x) ansl=mid,r=mid-1;
else l=mid+1;
} l=rk[c],r=n;
while(l<=r){
int mid=l+r>>1;
if(query(rk[c],mid)>=x) ansr=mid,l=mid+1;
else r=mid-1;
}
return query(root[b-x+1],root[a-1],1,n,ansl,ansr);
}
signed main(){
n=getint(),q=getint();
scanf("%s",s+1);
getsa(),getheight(),getst();
for(int i=1;i<=n;i++)
root[i]=modify(root[i-1],1,n,rk[i]);
while(q--){
int a=getint(),b=getint(),c=getint(),d=getint();
int l=1,r=min(b-a+1,d-c+1),ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(a,b,c,d,mid)) ans=mid,l=mid+1;
else r=mid-1;
} printf("%d\n",ans);
} return 0;
}
}