题目大意：给一个串和多组询问，每次询问S[a....b]的所有字串和S[c...d]这个字符串的最长公共前缀是多少
最长公共前缀啊，大概直接想到后缀数组二分RMQ之类的了
但是现在有一个问题比较恶心，就是“S[a....b]的所有字串“和“从a....b开始的所有字串”还不太一样，因为有结束位置的限制，比如说从a位置开始的最长公共前缀是2，而从b开始的很长，那在算的时候肯定会选择b，然而b的有效匹配长度是1，这样就出现了很不好的问题....
那就只好先二分枚举长度了
这样可以直接pass掉a...b中后面一部分开始的字串，然后前面的还没有限制了
问题就转化为了每次询问字符串中从a...B开头的字串和c开头的字串最长公共前缀有多长？
这就是个很经典的问题了
首先我们先要搞个后缀数组
然后在前后各做一次二分，求出从Rank[c]开始扩展，在保证“这段区间height数组最小值”大于等于“最开始二分的长度”的情况下，最远能向两边扩展到哪
这就得到了一个区间，我们只需要查这个区间内有没有符合SA[i]∈[a,B]的即可，这步可以用主席树来做
如果有，说明这个二分的长度可以达到
如果没有，那就说明不可以
时间复杂度O(NlogN^2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200010
using namespace std;
int sa[N],wa[N],wb[N],c[N];
int n,m;
char s[N];
void buildsa()
{
int i,k,p,*x=wa,*y=wb;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=s[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
for(k=1;k<=n;k*=2)
{
p=0;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]]++;
for(i=1;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
p=1;swap(x,y);
x[sa[0]]=0;
for(i=1;i<n;i++)
{
if(y[sa[i]]==y[sa[i-1]]&&((sa[i]+k>=n&&sa[i-1]+k>=n)||(sa[i]+k<n&&sa[i-1]+k<n&&y[sa[i]+k]==y[sa[i-1]+k])))
x[sa[i]]=p-1;
else x[sa[i]]=p,p++;
}
if(p>=n) break;
m=p;
}
}
int rnk[N],h[N];
void geth()
{
int i,j,k=0;
for(i=0;i<n;i++) rnk[sa[i]]=i;
for(i=0;i<n;i++)
{
k=max(k-1,0);
if(rnk[i]==0) continue;
while(s[i+k]==s[sa[rnk[i]-1]+k]) k++;
h[rnk[i]]=k;
}
}
int lo[N];
int rmq[N][21];
int RMQ(int x,int y)
{
int l=lo[y-x+1];
return min(rmq[x][l],rmq[y-(1<<l)+1][l]);
}
int rt[N],ch[N*20][2],sum[N*20],cn;
void pup(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]];}
void addnew(int x,int &y,int l,int r,int v,int w)
{
cn++;y=cn;
if(l==r)
{
sum[y]=sum[x]+w;
return;
}
ch[y][0]=ch[x][0];ch[y][1]=ch[x][1];
int mid=(l+r)>>1;
if(v<=mid) addnew(ch[x][0],ch[y][0],l,mid,v,w);
else addnew(ch[x][1],ch[y][1],mid+1,r,v,w);
pup(y);
}
int check(int x,int y,int L,int R,int l,int r)
{
if(L==l&&R==r) return sum[y]-sum[x];
int mid=(L+R)>>1;
if(r<=mid) return check(ch[x][0],ch[y][0],L,mid,l,r);
else if(l>mid) return check(ch[x][1],ch[y][1],mid+1,R,l,r);
else return check(ch[x][0],ch[y][0],L,mid,l,mid)+check(ch[x][1],ch[y][1],mid+1,R,mid+1,r);
}
bool checkit(int k,int p,int q,int x,int y)
{
int L,R,mid,l,r;
int FG=rnk[x];
if(h[FG]<k) L=FG;
else
{
l=1;r=FG;
while(l<r)
{
mid=(l+r)>>1;
if(RMQ(mid,FG)<k) l=mid+1;
else r=mid;
}
L=l-1;
}
if(FG==n-1||h[FG+1]<k) R=FG;
else
{
l=FG+1;r=n-1;
while(l<r)
{
mid=(l+r)>>1;
if(RMQ(FG+1,mid)<k) r=mid;
else l=mid+1;
}
R=l-1;
}
if(check(rt[L],rt[R+1],0,n,p,q)>0) return true;
return false;
}
int main()
{
int Q;
scanf("%d%d",&n,&Q);
m=255;
scanf("%s",s);
int i,j,x,y,p,q;
buildsa();
geth();
for(i=1;i<=n;i++)
lo[i]=(int)(log2(i));
for(i=0;i<n;i++)
rmq[i][0]=h[i];
for(j=1;j<=20;j++)
for(i=0;i+(1<<(j-1))<n;i++)
rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
int l,r,mid,L,R;
for(i=1;i<=n;i++)
addnew(rt[i-1],rt[i],0,n,sa[i-1],1);
int Z,Y,M;
while(Q--)
{
scanf("%d%d%d%d",&p,&q,&x,&y);
x--;y--;p--;q--;
Z=0;Y=min(y-x+1,q-p+1)+1;
while(Z<Y)
{
M=(Z+Y)>>1;
if(checkit(M,p,q-M+1,x,y)) Z=M+1;
else Y=M;
}
printf("%d\n",Z-1);
}
}