后缀数组。
复习了后缀数组后发现这题真的很好写。
我们只需要将c依次向前向后扩展，找落在[a,b]区间内的最大值，遍历过程中不断用height数组更新。
复杂度就是后缀数组，比主席树的快多了。
By：大奕哥
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 using namespace std; 7 const int N=1e5+10; 8 inline int read() 9 { 10 char ch;ch=getchar();int x=0; 11 while(ch<'0'||ch>'9')ch=getchar(); 12 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 13 return x; 14 } 15 int wv[N],wu[N],wa[N],wb[N],sa[N],rank[N],height[N],r[N]; 16 inline int cmp(int *r,int a,int b,int l) 17 { 18 return r[a]==r[b]&&r[a+l]==r[b+l]; 19 } 20 void da(int *r,int *sa,int n,int m) 21 { 22 int i,j,p;int *x=wa,*y=wb; 23 for(i=0;i<m;++i)wu[i]=0; 24 for(i=0;i<n;++i)wu[x[i]=r[i]]++; 25 for(i=1;i<m;++i)wu[i]+=wu[i-1]; 26 for(i=n-1;i>=0;--i)sa[--wu[x[i]]]=i; 27 for(j=1,p=1;p<n;j<<=1,m=p) 28 { 29 for(p=0,i=n-j;i<n;++i)y[p++]=i; 30 for(i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j; 31 for(i=0;i<n;++i)wv[i]=x[y[i]]; 32 for(i=0;i<m;++i)wu[i]=0; 33 for(i=0;i<n;++i)wu[wv[i]]++; 34 for(i=1;i<m;++i)wu[i]+=wu[i-1]; 35 for(i=n-1;i>=0;--i)sa[--wu[wv[i]]]=y[i]; 36 for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;++i) 37 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 38 } 39 return; 40 } 41 void calcHeight(int *rank,int *sa,int n) 42 { 43 int i,j,k=0; 44 for(i=1;i<=n;++i)rank[sa[i]]=i; 45 for(i=0;i<n;height[rank[i++]]=k) 46 for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];++k); 47 return; 48 } 49 char s[N]; 50 void work(int a,int b,int c,int d,int n) 51 { 52 int len=0,tmp=N; 53 if(c>=a&&c<=b)len=max(len,min(d-c+1,b-c+1)); 54 for(int i=rank[c-1];i>=2;--i) 55 { 56 tmp=min(tmp,height[i]); 57 if(height[i]==0||tmp<=len)break; 58 if(sa[i-1]>=a-1&&sa[i-1]<=b-1) 59 { 60 len=max(len,min(min(min(tmp,height[i]),b-sa[i-1]),d-c+1)); 61 } 62 } 63 tmp=N; 64 for(int i=rank[c-1]+1;i<=n;++i) 65 { 66 tmp=min(tmp,height[i]); 67 if(height[i]==0||tmp<=len)break; 68 if(sa[i]>=a-1&&sa[i]<=b-1) 69 { 70 len=max(len,min(min(min(tmp,height[i]),b-sa[i]),d-c+1)); 71 } 72 } 73 printf("%d ",len); 74 } 75 int main() 76 { 77 int n,m,a,b,c,d; 78 n=read();m=read(); 79 scanf("%s",s); 80 int len=strlen(s); 81 for(int i=0;i<len;++i)r[i]=s[i];r[len]=0; 82 da(r,sa,len+1,216);calcHeight(rank,sa,len); 83 for(int i=1;i<=m;++i) 84 { 85 a=read();b=read();c=read();d=read(); 86 work(a,b,c,d,len); 87 } 88 return 0; 89 }