题意：
有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。“主题”是整个音符序列的一个子串，它需要满足如下条件：
1.长度至少为5个音符
2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。)
3.重复出现的同一主题不能有公共部分。
题解：
和最长重复子串（可重叠）的思路是一样的。
只是我们需要在height数组中二分最小区间。若mid为二分值，删除所有的height[i]<mid的部分，会把height数组分成很多块，显然，我们要求的lcp一定在同一块内
（后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱，正规的说，令x=rank[i],y=rank[j]，x<y,那么
lcp(i,j)=min(height[x+1],height[x+2]...height[y])。lcp(i,i)=n-sa[i]。）
具体就做法是：若同一块内的sa的最大值与最小值的差>=mid，则判定成功，反之则失败
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 7 #define N 50050 8 9 using namespace std; 10 11 int r[N],wa[N],wc[N],wv[N],sa[N],wb[N],height[N],rank[N]; 12 int n; 13 14 inline bool cmp(int *r,int a,int b,int l) 15 { 16 return r[a]==r[b]&&r[a+l]==r[b+l]; 17 } 18 19 inline void da(int *r,int *sa,int n,int m) 20 { 21 int i,j,p,*x=wa,*y=wb,*t; 22 for(i=0;i<m;i++) wc[i]=0; 23 for(i=0;i<n;i++) wc[x[i]=r[i]]++; 24 for(i=1;i<m;i++) wc[i]+=wc[i-1]; 25 for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i; 26 for(j=1,p=1;p<n;j<<=1,m=p) 27 { 28 for(i=n-j,p=0;i<n;i++) y[p++]=i; 29 for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; 30 for(i=0;i<n;i++) wv[i]=x[y[i]]; 31 for(i=0;i<m;i++) wc[i]=0; 32 for(i=0;i<n;i++) wc[wv[i]]++; 33 for(i=1;i<m;i++) wc[i]+=wc[i-1]; 34 for(i=n-1;i>=0;i--) sa[--wc[wv[i]]]=y[i]; 35 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) 36 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 37 } 38 } 39 40 inline void getheight(int *r,int *sa,int n) 41 { 42 int i,j,k=0; 43 for(i=1;i<=n;i++) rank[sa[i]]=i; 44 for(i=0;i<n;height[rank[i++]]=k) 45 for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); 46 } 47 48 inline bool check(int x) 49 { 50 int mx=sa[1],mn=sa[1]; 51 for(int i=2;i<n;i++) 52 { 53 if(height[i]<x) mx=mn=sa[i]; 54 else 55 { 56 mx=max(mx,sa[i]); 57 mn=min(mn,sa[i]); 58 if(mx-mn>=x) return true; 59 } 60 } 61 return false; 62 } 63 64 inline void getans() 65 { 66 int l=4,r=(n>>1)+1,mid,res; 67 while(l<=r) 68 { 69 mid=(l+r)>>1; 70 if(check(mid)) res=mid,l=mid+1; 71 else r=mid-1; 72 } 73 if(res<4) puts("0"); 74 else printf("%d\n",res+1); 75 } 76 77 inline void go() 78 { 79 n--; 80 for(int i=0;i<=n;i++) scanf("%d",&r[i]); 81 if(n<10) {puts("0");return;} 82 for(int i=0;i<n;i++) r[i]=r[i]-r[i+1]+90; 83 r[n]=0; 84 da(r,sa,n+1,200); 85 getheight(r,sa,n); 86 getans(); 87 } 88 89 int main() 90 { 91 while(scanf("%d",&n),n) go(); 92 return 0; 93 }