题目大意
找到一个连续的子序列连续出现过两次，且这两次不相交，只要子序列中每个数都加/减一个数得到一个新的序列，也可以看作是相同的
那么也就是说这道题目可以转化成找到两个子序列，这两个子序列中每个数前后的差值是相等的
所以我们可以求所有数两两之间的差值，然后根据这个值建立后缀数组后，二分答案来解决问题
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 const int N = 20010; 7 int rank[N] , sa[N] , height[N]; 8 int wa[N] , wb[N] , tmp[N] , wv[N]; 9 int a[N] , b[N]; 10 11 int cmp(int *r , int a , int b , int l) 12 { 13 return r[a]==r[b] && r[a+l]==r[b+l]; 14 } 15 16 void getSa(int *r , int *sa , int n , int m) 17 { 18 int i,j,p; 19 int *x=wa , *y=wb , *t; 20 for(i=0 ; i<m ; i++) tmp[i]=0; 21 for(i=0 ; i<n ; i++) tmp[x[i]=r[i]]++; 22 for(i=1 ; i<m ; i++) tmp[i]+=tmp[i-1]; 23 for(i=n-1 ; i>=0 ; i--) sa[--tmp[x[i]]]=i; 24 25 //初始p=1是防止只有一个元素就可以退出循环的 26 for(p=1,j=1 ; p<n ; j*=2,m=p){ 27 //对第二关键字排序 28 p=0; 29 for(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 32 for(i=0 ; i<n ; i++) wv[i]=x[y[i]]; 33 for(i=0 ; i<m ; i++) tmp[i]=0; 34 for(i=0 ; i<n ; i++) tmp[wv[i]]++; 35 for(i=1 ; i<m ; i++) tmp[i]+=tmp[i-1]; 36 for(i=n-1 ; i>=0 ; i--) sa[--tmp[wv[i]]]=y[i]; 37 t=x,x=y,y=t; 38 x[sa[0]]=0; 39 for(p=1,i=1 ; i<n ; i++) 40 x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++; 41 } 42 43 return; 44 } 45 46 void callHeight(int *r,int *sa,int n) 47 { 48 int i,j,k=0; 49 for(i=1 ; i<=n ; i++) rank[sa[i]]=i; 50 51 for(i=0 ; i<n ; height[rank[i++]]=k) 52 for(k?k--:0 , j=sa[rank[i]-1] ; r[i+k]==r[j+k] ; k++); 53 return; 54 } 55 56 bool check(int m , int n) 57 { 58 int l=sa[0] , r=sa[0]; 59 for(int i=1 ; i<n ; i++){ 60 if(height[i]<m){ 61 l=sa[i] , r=sa[i]; 62 } 63 else{ 64 l=min(sa[i] , l); 65 r=max(sa[i] , r); 66 if(r-l>m) return true; 67 } 68 } 69 return false; 70 } 71 72 int main() 73 { 74 // freopen("a.in" , "r" , stdin); 75 int n; 76 while(scanf("%d" , &n) , n) 77 { 78 for(int i=0 ; i<n ; i++) scanf("%d" , &a[i]); 79 for(int i=0 ; i<n-1 ; i++) b[i]=a[i+1]-a[i]+90; 80 b[n-1]=0; 81 getSa(b,sa,n,200); 82 callHeight(b,sa,n-1); 83 84 int l=0 , r=n , ans=0; 85 while(l<=r){ 86 int m=(l+r)>>1; 87 if(!check(m,n)) r=m-1; 88 else{ 89 ans=m; 90 l=m+1; 91 } 92 } 93 if(ans>=4) printf("%d " , ans+1); 94 else puts("0"); 95 } 96 return 0; 97 }