題目大意：給一個串和多組詢問，每次詢問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);
}
}