题目大意：求最长的重复字串，要求：1.这两个重复子串不重叠；2这两个重复字串不要求相同，只要对应的差值一样即可。比如，字符串1 2 8 3 100 3 9 4, 1 2 8 和3 9 4就是符合条件的长度最长的。
(1)要先把串转换一下，根据题目的性质，应该把输入得到的
串前后相减得到方便求解的新的串——设其为s，再求该串s中最长的
不重叠重复子串。由于不能重叠，导致height数组的最大值不一定是
解，因为相邻两串可能会重叠。
(2) 二分答案，判断是否存在满足条件的长度为len的子串时，其实就是判断height数组中是否存在连续的值大于等于len（这样就保证了公共前缀长度大于等于len）并且他们之间的间隔大于等于len（这样就保证了不重叠）。
贴下鄙人的代码
╭︿︿︿╮
{/ ︿︿ /}
( (oo) )
︶ ︶ ︶
╭︿︿︿╮
{/ ︿︿ /}
( (oo) )
︶ ︶ ︶
╭︿︿︿╮
{/ ︿︿ /}
( (oo) )
︶ ︶ ︶
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 20000+5
char s[maxn];
int sa[maxn],h[maxn],height[maxn],rank[maxn];
int k,n;
bool cmp1(const int & a,const int & b)
{
return (s[a]<s[b]);
}
bool cmp2(const int & a,const int & b)
{
return (rank[a]<rank[b] || (rank[a]==rank[b]&&
(a+k<n?rank[a+k]:-1)<(b+k<n?rank[b+k]:-1)));
}
void suffixArray()
{
int i,j;
for(i=0;i<n;i++)
sa[i]=i;
sort(sa,sa+n,cmp1);
for(i=0;i<n;i++)
{
if(i==0||s[sa[i]]!=s[sa[i-1]])
rank[sa[i]]=i;
else rank[sa[i]]=rank[sa[i-1]];
}
for(k=1;k<n;k*=2)
{
sort(sa,sa+n,cmp2);
for(i=0;i<n;i++)
{
if( i==0 || (cmp2(sa[i],sa[i-1])||cmp2(sa[i-1],sa[i])) )
h[sa[i]]=i;
else h[sa[i]]=h[sa[i-1]];
}
memcpy(rank, h, n * sizeof(int));
}
height[0] = 0;
for(i = 0, j = 0; i < n; i++)
{
if(rank[i]>0)
{
while(s[sa[rank[i] - 1] + j] == s[i + j])
j++;
height[rank[i]] = j;
if(j > 0) j--;
}
}
}
bool ok(int len)
{
int maxIndex=0,minIndex=INT_MAX;
for(int i=1;i<n;i++)
{
if(height[i]<len)
{
maxIndex=0,minIndex=INT_MAX;
}
else
{
maxIndex=max(sa[i],maxIndex);
maxIndex=max(sa[i-1],maxIndex);
minIndex=min(sa[i],minIndex);
minIndex=min(sa[i-1],minIndex);
if(maxIndex-minIndex>=len)
return 1;
}
}
return 0;
}
int binarySearch()
{
int low=0,up=n/2;
int mid;
while(low<up)
{
mid=(low+up+1)>>1;
if(ok(mid))
low=mid;
else up=mid-1;
}
return low;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=0;i<n;i++)
scanf("%d",&s[i]);
for(i=1;i<n;i++)
s[i-1]=s[i]-s[i-1]+88;
s[n-1]=0;
suffixArray();
if(!ok(4))
printf("0\n");
else
printf("%d\n",binarySearch()+1);
}
return 0;
}