POJ1743 Musical Theme【二分】【后缀数组】

题意

有N(1 <= N <=20000)个音符的序列来表示一首乐曲，每个音符都是1…88范围内的整数，现在要找一个重复的主题。
“主题”是整个音符序列的一个子串，它需要满足如下条件：
1.长度至少为5个音符
2.在乐曲中重复出现(可能经过转调，“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。)
3.重复出现的同一主题不能有公共部分。

思路

后缀数组入门题目
先转化成相邻两项的差值，然后就是找不可重叠重复子串。
来自论文的思路
先二分答案，把题目变成判定性问题：判断是否存在两个长度为k的子串是相同的，且不重叠。解决这个问题的关键还是利用height数组。把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k。例如，字符串为“aabaaaab”，当 k=2时，后缀分成了4组，如图5所示。

容易看出，有希望成为最长公共前缀不小于k的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的sa值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为O(nlogn)。

AC_code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 20005
int ss[maxn];
int sa[maxn],c[maxn];
int rank[maxn],height[maxn];
int t1[maxn], t2[maxn];
void build_sa(int s[],int n,int m) {// 字符串 字符串长度+1 最大字符+1
	int i,j,p,*x=t1,*y=t2;
	for(i=0; i<m; i++)c[i]=0;
	for(i=0; i<n; i++)c[x[i]=s[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;
		for(i=n-j; i<n; i++)y[p++]=i;
		for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		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];
		swap(x,y);
		p=1;
		x[sa[0]]=0;
		for(i=1; i<n; i++)
			x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
		if(p>=n)break;
		m=p;
	}
}
void getHeight(int s[],int n) {
	int i,j,k=0;
	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(s[i+k]==s[j+k])k++;
		height[rank[i]]=k;
	}
}
bool check(int k, int n){
	int maxx = sa[1];
	int minn = sa[1];
	for(int i = 2; i <= n; i++){
		if(height[i] < k){
			maxx = minn = sa[i];
		}else{
			minn = min(minn, sa[i]);
			maxx = max(maxx, sa[i]);
			if(maxx - minn > k) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	int n;
	while(~scanf("%d", &n)) {
		if(n == 0) break;
		int maxx = -1;
		for(int i = 0; i < n; i++) {
			scanf("%d", &ss[i]);
		}
		for(int i = n - 1; i > 0; i--) {
			ss[i] = ss[i] - ss[i-1] + 90;
		}
		n--;
		for(int i = 0; i < n; i++) {
			ss[i] =ss[i+1];
		}
		ss[n] = 0;
		build_sa(ss, n+1, 200);
		getHeight(ss, n);
		int ans = -1;
		int l = 1, r = n/2;
		while(l <= r) {
			int mid = (l+r) / 2;
			if(check(mid, n)) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if(ans < 4) puts("0");
		else {
			printf("%d\n", ans+1);
		}
	}
	return 0;
}