后缀数组求最长重复且不重叠子串。
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的代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,ans;
int s[];
int sa[],rk[];
int tr[],h[]; int cmp(int x,int y,int k)
{
if(x+k>n||y+k>n)return ;
return rk[x]==rk[y]&&rk[x+k]==rk[y+k];
} void cal()
{
int i,cnt;
for(i=;i<=n;i++)h[s[i]]++;
for(cnt=,i=;i<=;i++)if(h[i])tr[i]=++cnt;
for(i=;i<=;i++)h[i]+=h[i-];
for(i=;i<=n;i++)rk[i]=tr[s[i]],sa[h[s[i]]--]=i;
for(int k=;cnt!=n;k<<=)
{
for(i=;i<=n;i++)h[i]=;
for(i=;i<=n;i++)h[rk[i]]++;
for(i=;i<=n;i++)h[i]+=h[i-];
for(i=n;i;i--)if(sa[i]>k)tr[sa[i]-k]=h[rk[sa[i]-k]]--;
for(i=;i<=k;i++)tr[n-i+]=h[rk[n-i+]]--;
for(i=;i<=n;i++)sa[tr[i]]=i;
for(cnt=,i=;i<=n;i++)tr[sa[i]]=cmp(sa[i],sa[i-],k)?cnt:++cnt;
for(i=;i<=n;i++)rk[i]=tr[i];
}
for(i=;i<=n;i++)h[i]=;
for(i=;i<=n;i++)
{
if(rk[i]==)continue;
for(int j=max(,h[rk[i-]]-);;j++)
{
if(s[i+j-]==s[sa[rk[i]-]+j-])h[rk[i]]=j;
else break;
}
}
} int check(int k)
{
if(k>n)return ;
int l,r;
l=r=sa[];
for(int i=;i<=n;i++)
{
if(h[i]>=k)
{
l=min(l,sa[i]);
r=max(r,sa[i]);
if(r-l>k)return ;
}else l=r=sa[i];
}
return ;
} int main()
{
scanf("%d",&n);
while(n)
{
memset(h,,sizeof(h));
memset(tr,,sizeof(tr));
memset(rk,,sizeof(rk));
memset(sa,,sizeof(sa));
ans=;
for(int i=;i<=n;i++)scanf("%d",&s[i]);
for(int i=;i<n;i++)s[i]=s[i+]-s[i]+;
cal();
for(int i=;i>=;i--)
if(check(ans|(<<i)))ans|=(<<i);
ans=(ans+)>=?(ans+):;
printf("%d\n",ans);
scanf("%d",&n);
}
return ;
}