题目链接：http://poj.org/problem?id=1743
题目理解起来比较有困难，其实就是求最长有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。
* “主题”是整个音符序列的一个子串，它需要满足如下条件：
* 1.长度至少为5个音符
* 2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。)
* 3.重复出现的同一主题不能有公共部分。
*
所以1，2，3，4，5 和 6，7，8，9，10 是同一个主题
思路：
先转化成相邻两项的差值，然后就是找不可重叠重复子串。
详细解释可以参考：http://hi.baidu.com/ahnkftravhdhkyr/item/346115451d98e8fedc0f6ccd
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 20010 int wa[maxn],wb[maxn],wv[maxn],wq[maxn];
int height[maxn];
int s[maxn];
int rank[maxn];
int sa[maxn];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *s,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=;i<m;i++) wq[i]=;
for(i=;i<n;i++) wq[x[i]=s[i]]++;
for(i=;i<m;i++) wq[i]+=wq[i-];
for(i=n-;i>=;i--) sa[--wq[x[i]]]=i; for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=;i<n;i++) wv[i]=x[y[i]];
for(i=;i<m;i++) wq[i]=;
for(i=;i<n;i++) wq[wv[i]]++;
for(i=;i<m;i++) wq[i]+=wq[i-];
for(i=n-;i>;i--) sa[--wq[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
} return ;
}
void getHeight(int *s ,int n)
{
int i,j ,k=;
for(i=;i<=n;i++) rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k) k--;
j=sa[rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
bool check(int n,int k)
{
int Max=sa[],Min=sa[];
for(int i=;i<=n;i++)
{
if(height[i]<k) Max=Min=sa[i];
else
{
if(sa[i]<Min)Min=sa[i];
if(sa[i]>Max)Max=sa[i];
if(Max-Min>k) return ;
}
}
return ;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF && n)
{
for(int i=;i<n;i++) scanf("%d",&s[i]);
for(int i=;i<n-;i++) s[i]=s[i+]-s[i]+; n--;
s[n]=;
da(s,sa,n+,);
getHeight(s,n);
int ans=-;
int low=,high=n/;
while(low<=high)
{
int mid=(low+high)/;
if(check(n,mid))
{
ans=mid;
low=mid+;
}
else high=mid-;
}
if(ans<) cout<<""<<endl;
else cout<<ans+<<endl;
}
return ;
}