后缀数组求最长重复且不重叠子串。
1.子串可以“变调”（即1 3 6和3 5 8视作相同）。解决办法：求字符串相邻元素的差形成新串。用新字符串求解最长重复子串即可。
2.最长重复子串不能重叠。解决办法：用sa数组判断开始位置。
倍增答案即可，从1到n枚举height，记录子串开始的最左端、最右端。
如果找到了两个后缀，其公共前缀长度大于k，且其开始位置之间的间隔大于k，就满足条件。
由height数组的性质可得：要使x、y的公共前缀长度大于k，则需要h[x+1]、h[x+2]......h[y]全部大于k。
所以只要有一个没有大于k，就得重新开始。即：重置子串开始的最左端、最右端。
最后答案需要+1，并判断是否大于等于5（题意要求）。
注意poj的数据范围比洛谷上大，而且有多组测试数据。
下面只给出poj1743的代码。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int n,ans; 7 int s[20005]; 8 int sa[20005],rk[20005]; 9 int tr[20005],h[20005]; 10 11 int cmp(int x,int y,int k) 12 { 13 if(x+k>n||y+k>n)return 0; 14 return rk[x]==rk[y]&&rk[x+k]==rk[y+k]; 15 } 16 17 void cal() 18 { 19 int i,cnt; 20 for(i=1;i<=n;i++)h[s[i]]++; 21 for(cnt=0,i=1;i<=200;i++)if(h[i])tr[i]=++cnt; 22 for(i=1;i<=200;i++)h[i]+=h[i-1]; 23 for(i=1;i<=n;i++)rk[i]=tr[s[i]],sa[h[s[i]]--]=i; 24 for(int k=1;cnt!=n;k<<=1) 25 { 26 for(i=1;i<=n;i++)h[i]=0; 27 for(i=1;i<=n;i++)h[rk[i]]++; 28 for(i=1;i<=n;i++)h[i]+=h[i-1]; 29 for(i=n;i;i--)if(sa[i]>k)tr[sa[i]-k]=h[rk[sa[i]-k]]--; 30 for(i=1;i<=k;i++)tr[n-i+1]=h[rk[n-i+1]]--; 31 for(i=1;i<=n;i++)sa[tr[i]]=i; 32 for(cnt=0,i=1;i<=n;i++)tr[sa[i]]=cmp(sa[i],sa[i-1],k)?cnt:++cnt; 33 for(i=1;i<=n;i++)rk[i]=tr[i]; 34 } 35 for(i=1;i<=n;i++)h[i]=0; 36 for(i=1;i<=n;i++) 37 { 38 if(rk[i]==1)continue; 39 for(int j=max(1,h[rk[i-1]]-1);;j++) 40 { 41 if(s[i+j-1]==s[sa[rk[i]-1]+j-1])h[rk[i]]=j; 42 else break; 43 } 44 } 45 } 46 47 int check(int k) 48 { 49 if(k>n)return 0; 50 int l,r; 51 l=r=sa[1]; 52 for(int i=2;i<=n;i++) 53 { 54 if(h[i]>=k) 55 { 56 l=min(l,sa[i]); 57 r=max(r,sa[i]); 58 if(r-l>k)return 1; 59 }else l=r=sa[i]; 60 } 61 return 0; 62 } 63 64 int main() 65 { 66 scanf("%d",&n); 67 while(n) 68 { 69 memset(h,0,sizeof(h)); 70 memset(tr,0,sizeof(tr)); 71 memset(rk,0,sizeof(rk)); 72 memset(sa,0,sizeof(sa)); 73 ans=0; 74 for(int i=1;i<=n;i++)scanf("%d",&s[i]); 75 for(int i=1;i<n;i++)s[i]=s[i+1]-s[i]+90; 76 cal(); 77 for(int i=20;i>=0;i--) 78 if(check(ans|(1<<i)))ans|=(1<<i); 79 ans=(ans+1)>=5?(ans+1):0; 80 printf("%d ",ans); 81 scanf("%d",&n); 82 } 83 return 0; 84 }