Description

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

Input

输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,

字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n

Output

 对于每一次询问，输出答案。

Sample Input

5 5

aaaaa

1 1 1 5

1 5 1 1

2 3 2 3

2 4 2 3

2 3 2 4

Sample Output

1

1

2

2

2

Solution

设$suf_i$表示后缀$i$，

首先考虑二分一个答案$mid$，那么现在问题转化成求$suf_a$到$suf_{b-mid+1}$的这些个后缀中，是否有一个后缀和$suf(c)$的$lcp$大于等于$mid$。

设$SA_i$表示后缀排序排名为$i$的后缀，$Rank_i$表示$suf_i$的后缀排序排名。

由于对于$suf_c$，我们可以用二分+$ST$表求出后缀排序中的可行区间，可行区间内的后缀和$suc_c$的$lcp$长度都大于等于$mid$。现在问题转化为了求$suf_a$到$suf_{b-mid+1}$的这些后缀是否哪个后缀的$Rank$值在可行区间内，这个用一个主席树就好了。

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (100009)  5 using namespace std;  6   7 struct Sgt{
   int ls,rs,val;}Segt[N*18];  8 int Root[N],sgt_num;  9 int n,q,m=26,a,b,c,d; 10 int ST[N][18],LOG2[N]; 11 int wa[N],wb[N],wt[N],SA[N],Height[N],Rank[N]; 12 char r[N]; 13  14 inline int read() 15 { 16     int x=0,w=1; char c=getchar(); 17     while (c<'0' || c>'9') {
   if (c=='-') w=-1; c=getchar();} 18     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar(); 19     return x*w; 20 } 21  22 bool cmp(int *y,int a,int b,int k) 23 { 24     int arank1=y[a]; 25     int brank1=y[b]; 26     int arank2=a+k>=n?-1:y[a+k]; 27     int brank2=b+k>=n?-1:y[b+k]; 28     return arank1==brank1 && arank2==brank2; 29 } 30  31 void Build_SA() 32 { 33     int *x=wa,*y=wb; 34     for (int i=0; i
        
         =0; --i) SA[--wt[x[i]]]=i; 38      39     for (int j=1; j<=n; j<<=1) 40     { 41         int p=0; 42         for (int i=n-j; i
         
          =j) y[p++]=SA[i]-j; 44          45         for (int i=0; i
          
           =0; --i) SA[--wt[x[y[i]]]]=y[i]; 49 50 m=1; swap(x,y); 51 x[SA[0]]=0; 52 for (int i=1; i
           
            =n) break; 55 } 56 } 57 58 void Build_Height() 59 { 60 for (int i=0; i
            
             >1]+1; 75 for (int i=0; i
             
              >1; 94 if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x); 95 else Segt[now].rs=Update(Segt[now].rs,mid+1,r,x); 96 return now; 97 } 98 99 int Query(int u,int v,int l,int r,int l1,int r1)100 {101 if (l>r1 || r
              
               >1;104 return Query(Segt[u].ls,Segt[v].ls,l,mid,l1,r1)+Query(Segt[u].rs,Segt[v].rs,mid+1,r,l1,r1);105 }106 107 bool check(int lim)108 {109 int l,r,L,R;110 l=0,r=Rank[c]-1,L=Rank[c];111 while (l<=r)112 {113 int mid=(l+r)>>1;114 if (Query(mid+1,Rank[c])>=lim) L=mid,r=mid-1;115 else l=mid+1;116 }117 l=Rank[c]+1,r=n-1,R=Rank[c];118 while (l<=r)119 {120 int mid=(l+r)>>1;121 if (Query(Rank[c]+1,mid)>=lim) R=mid,l=mid+1;122 else r=mid-1;123 }124 if (Query(Root[a],Root[b-lim+2],0,n,L,R)) return true;125 return false;126 }127 128 int main()129 {130 n=read(); q=read();131 scanf("%s",r);132 Build_SA(); Build_Height();133 Build_ST();134 for (int i=1; i<=n; ++i)135 Root[i]=Update(Root[i-1],0,n,Rank[i-1]);136 while (q--)137 {138 a=read()-1; b=read()-1; c=read()-1; d=read()-1;139 int l=1,r=min(b-a+1,d-c+1),ans=0;140 while (l<=r)141 {142 int mid=(l+r)>>1;143 if (check(mid)) ans=mid, l=mid+1;144 else r=mid-1;145 }146 printf("%d\n",ans);147 }148 }