poj1743 Musical Theme 后缀数组的应用(求最长不重叠重复子串)

题目理解起来比较有困难，其实就是求最长有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

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 #define maxn 20010
 7 
 8 int wa[maxn],wb[maxn],wv[maxn],wq[maxn];
 9 int height[maxn];
10 int s[maxn];
11 int rank[maxn];
12 int sa[maxn];
13 bool cmp(int *r,int a,int b,int l)
14 {return r[a]==r[b]&&r[a+l]==r[b+l];}
15 void da(int *s,int *sa,int n,int m)
16 {
17 int i,j,p,*x=wa,*y=wb,*t;
18 for(i=0;i<m;i++) wq[i]=0;
19 for(i=0;i<n;i++) wq[x[i]=s[i]]++;
20 for(i=0;i<m;i++) wq[i]+=wq[i-1];
21 for(i=n-1;i>=0;i--) sa[--wq[x[i]]]=i;
22 
23 for(j=1,p=1;p<n;j*=2,m=p)
24 {
25 for(p=0,i=n-j;i<n;i++) y[p++]=i;
26 for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
27 for(i=0;i<n;i++) wv[i]=x[y[i]];
28 for(i=0;i<m;i++) wq[i]=0;
29 for(i=0;i<n;i++) wq[wv[i]]++;
30 for(i=1;i<m;i++) wq[i]+=wq[i-1];
31 for(i=n-1;i>0;i--) sa[--wq[wv[i]]]=y[i];
32 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
33 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
34 }
35 
36 return ;
37 }
38 void getHeight(int *s ,int n)
39 {
40 int i,j ,k=0;
41 for(i=1;i<=n;i++) rank[sa[i]]=i;
42 for(i=0;i<n;i++)
43 {
44 if(k) k--;
45 j=sa[rank[i]-1];
46 while(s[i+k]==s[j+k]) k++;
47 height[rank[i]]=k;
48 }
49 }
50 bool check(int n,int k)
51 {
52 int Max=sa[1],Min=sa[1];
53 for(int i=2;i<=n;i++)
54 {
55 if(height[i]<k) Max=Min=sa[i];
56 else
57 {
58 if(sa[i]<Min)Min=sa[i];
59 if(sa[i]>Max)Max=sa[i];
60 if(Max-Min>k) return 1;
61 }
62 }
63 return 0;
64 }
65 int main()
66 {
67 int n;
68 while(scanf("%d",&n)!=EOF && n)
69 {
70 for(int i=0;i<n;i++) scanf("%d",&s[i]);
71 for(int i=0;i<n-1;i++) s[i]=s[i+1]-s[i]+100;
72 
73 n--;
74 s[n]=0;
75 da(s,sa,n+1,200);
76 getHeight(s,n);
77 int ans=-1;
78 int low=4,high=n/2;
79 while(low<=high)
80 {
81 int mid=(low+high)/2;
82 if(check(n,mid))
83 {
84 ans=mid;
85 low=mid+1;
86 }
87 else high=mid-1;
88 }
89 if(ans<4) cout<<"0"<<endl;
90 else cout<<ans+1<<endl;
91 }
92 return 0;
93 }