题目链接：

题意：

给你一串数字，让你找最长的变化相同不重叠的子串，至少长度为5

题解：

处理数据后用后缀数组加二分答案，然后用height数组check答案，运用height数组求相同不重叠的子串经典运用

 

1 #include
      
        2 #include
       
         3 #define F(i,a,b) for(int i=a;i<=b;i++) 4 using namespace std; 5  6 namespace suffixarray{     7     #define FN(n) for(int i=0;i
        
         =0;i--)sa[--c[x[i]]]=i;13         for(int k=1,p;p=0,k<=n;k=p>=n?N:k<<1,m=p){14             for(int i=n-k;i
         
          =k)y[p++]=sa[i]-k;16             FN(m)c[i]=0;FN(n)c[x[y[i]]]++;FN(m)c[i+1]+=c[i];17             for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];18             swap(x,y),p=1,x[sa[0]]=0;19             for(int i=1;i
          
           b)a=b;}31 inline void upu(int &a,int b){
    if(a
           
            =x)39 {40 upd(l,sa[i]),upu(r,sa[i]);41 if(r-l>=x)return 1;42 }else l=r=sa[i];43 }44 return 0;45 }46 47 int main()48 {49 while(scanf("%d",&n),n)50 {51 F(i,0,n-1)scanf("%d",s+i);52 if(n<10){puts("0");continue;}53 F(i,0,n-2)s[i]=s[i+1]-s[i]+89;54 s[--n]=0,getsa(n+1,200);55 int l=4,r=n,mid;56 while(l<=r)mid=(l+r)>>1,check(mid)?l=mid+1:r=mid-1;57 printf("%d\n",l<5?0:l);58 }59 return 0;60 }