題目大意：求最長的重復字串，要求：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;
}