题意：
有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，现在要找一个重复的主题。
“主题”是整个音符序列的一个子串，它需要满足如下条件：
1.长度至少为5个音符
2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。)
3.重复出现的同一主题不能有公共部分。
思路:是要求最长不重叠重复的子串，如果没有不重叠的限制条件，那么height中的最大值即可
现在对于这题需要二分出答案，二分出最长重复子串的长度len，再把height数组按与len大小分组，再判断是否重叠
本题中利用height 值对后缀进行分组的方法很常用。
//704K250MS#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int MAXN=20010;const int inf = 0x3f3f3f3f;int t1[MAXN],t2[MAXN],c[MAXN];//求SA数组需要的中间变量，不需要赋值//待排序的字符串放在s数组中，从s[0]到s[n-1],长度为n,且最大值小于m,//除s[n-1]外的所有s[i]都大于0，r[n-1]=0//函数结束以后结果放在sa数组中bool cmp(int *r,int a,int b,int l){return r[a] == r[b] && r[a+l] == r[b+l];}void da(int str[],int sa[],int rank[],int height[],int n,int m){n++;int i, j, p, *x = t1, *y = t2;//第一轮基数排序，，如果s的最大值很大，可改为快速排序for(i = 0;i < m;i++) c[i] = 0;for(i = 0;i < n;i++) c[x[i] = str[i]]++;for(i = 1;i < m;i++) c[i] += c[i-1];for(i = n-1;i >= 0;i–) sa[–c[x[i]]] = i;for(j = 1;j <= n; j <<= 1){p = 0;//直接利用sa数组排序第二关键字for(i = n-j; i < n; i++) y[p++] = i;//后面的j个数第二关键字为空的最小for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] – j;//这样数组y保存的就是按照第二关键字排序的结果//基数排序第一关键字for(i = 0; i < m; i++) c[i] = 0;for(i = 0; i < n; i++) c[x[y[i]]]++;for(i = 1; i < m;i++) c[i] += c[i-1];for(i = n-1; i >= 0;i–) sa[–c[x[y[i]]]] = y[i];//根据sa和x数组计算新的x数组swap(x,y);p = 1; x[sa[0]] = 0;for(i = 1;i < n;i++)x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;if(p >= n) break;m = p;//下次基数排序的最大值}int k = 0;n–;for(i = 0;i <= n;i++) rank[sa[i]] = i;for(i = 0;i < n;i++){if(k) k–;j = sa[rank[i]-1];while(str[i+k] == str[j+k]) k++;height[rank[i]] = k;}}int rank[MAXN],height[MAXN];int r[MAXN];int sa[MAXN];bool ok(int x,int n){int maxn=sa[1],minn=sa[1];for(int rnk=2;rnk<=n;rnk++){if(height[rnk]>=x){minn=min(minn,sa[rnk]);maxn=max(maxn,sa[rnk]);if(maxn-minn>=x) return true;}else maxn=sa[rnk],minn=sa[rnk];}return false;}int main(){int n;while(scanf("%d",&n),n){for(int i=0;i<n;i++) scanf("%d",&r[i]);for(int i=0;i<n-1;i++) r[i]=r[i+1]-r[i]+90;n–;r[n]=0;da(r,sa,rank,height,n,180);int lb=0,ub=n/2+1;//二分区间定在题意区间外[1,n/2]while(ub-lb>1){int mid=(lb+ub)>>1;if(ok(mid,n)) lb=mid;else ub=mid;}if(lb<4) printf("0\n");else printf("%d\n",lb+1);}return 0;}
在时光的激流中，我们总会长大。
