题目：

本来只要查 ht[ ] 数组上的前驱和后继就行，但有长度的限制。可以二分答案解决！然后用主席树查区间内的 ht[ ] 的前驱和后继即可。（主席树弄对 rk 的权值线段树）

在主席树上走的复杂度应该不会比二分然后查看主席树的 log² 更差吧。

#include
     
      #include
      
       #include
       
        using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}int Mx(int a,int b){
   return a>b?a:b;}int Mn(int a,int b){
   return a
        
         k)tp[++tot]=sa[i]-k;      Rsort(n,nm);memcpy(tp,rk,sizeof rk);      nm=1;rk[sa[1]]=1;      for(int i=2;i<=n;i++)//i=2!!!!not i=1    {      int u=sa[i]+k,v=sa[i-1]+k;// if(u>n)u=0; if(v>n)v=0;      rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm;    }      if(nm==n)break;    }}void get_ht(int n){  for(int i=1,k=0,j;i<=n;i++)    {      if(rk[i]==1)continue;//      for((k?k--:0),j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++);      //i+k<=n&&j+k<=n      ht[rk[i]][0]=k;    }  for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;  bin[0]=1;for(int i=1;i<=lg[n];i++)bin[i]=bin[i-1]<<1;  //i<=lg[n] not bin[i-1]
         
          >1;  if(p<=mid)ins(ls[cr],ls[pr],l,mid,p);  else ins(rs[cr],rs[pr],mid+1,r,p);}int qry(int r1,int r2,int l,int r,int p){  if(sm[r2]-sm[r1]==0)return 0;  if(l==r)return l; int mid=l+r>>1,d=0;//d=0!!  if(p>mid)d=qry(rs[r1],rs[r2],mid+1,r,p);  if(d)return d;  return qry(ls[r1],ls[r2],l,mid,p);}int qry2(int r1,int r2,int l,int r,int p){  if(sm[r2]-sm[r1]==0)return 0;  if(l==r)return l; int mid=l+r>>1,d=0;  if(p<=mid)d=qry2(ls[r1],ls[r2],l,mid,p);//qry2 not qry  if(d)return d;  return qry2(rs[r1],rs[r2],mid+1,r,p);}int qry_ht(int l,int r){  if(l==r)return n-sa[l]+1;//n-sa[l]+1 not n-l+1!!!  int d=lg[r-l];  return Mn(ht[l+1][d],ht[r-bin[d]+1][d]);//l+1!!!not l}int main(){  int Q;n=rdn();Q=rdn();scanf("%s",s+1);//+1  get_sa(n);get_ht(n);  for(int i=1;i<=n;i++)ins(rt[i],rt[i-1],1,n,rk[i]);  int l1,r1,l2,r2;  while(Q--)    {      l1=rdn();r1=rdn();l2=rdn();r2=rdn();      int l=1,r=Mn(r1-l1+1,r2-l2+1),ans=0;      while(l<=r)    {      int mid=l+r>>1,d=r1-mid+1;      int p1=qry(rt[l1-1],rt[d],1,n,rk[l2]);      int p2=qry2(rt[l1-1],rt[d],1,n,rk[l2]);      int tmp=Mx((p1?qry_ht(p1,rk[l2]):0),(p2?qry_ht(rk[l2],p2):0));      if(tmp>=mid)ans=mid,l=mid+1;      else r=mid-1;    }      printf("%d\n",ans);    }  return 0;}