POJ-1743 Musical Theme 后缀数组求不可重叠最长重复子串

POJ-1743 Musical Theme 后缀数组求不可重叠最长重复子串

题意

给出一段乐曲，计算其中最长“主题”的长度

主题需要满足

• 长度至少为5个字符
• 在乐曲中重复出现（可能经过转调）
• 重复出现的同一主题不能有公共部分

所谓“转调”，是指每个音符都被加上或者减去同个值。

乐曲中的每个音符都是1到88的整数

给出N，表示这段乐曲有N个音符，后给出整数

[1leq nleq 20000 ]

分析

首先转调，可以转化为差分做，再把整个乐曲看成一个字符串，问题就变成了字符串中不可重叠的最长重复子串，这个问题在罗老师的经典论文中已经详细说明，这里说几个注意点

• 需要特判1
• 处理这类问题通常用int代替char
• 用刘汝佳老师的模板，通常需要加入一个'$'，若是int，则是0
• 将问题转化为判定性问题，分组 是处理后缀数组问题的常用手段

代码

int s[maxn],p[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn],n;

void build_sa(int m){
	int *x = t,*y = t2;
	for(int i = 0;i < m;i++) c[i] = 0;
	for(int i = 0;i < n;i++) c[x[i] = s[i]]++;
	for(int i = 1;i < m;i++) c[i] += c[i -1];
	for(int i = n - 1;i >= 0;i--) sa[--c[x[i]]] = i;
	for(int k = 1;k <= n;k <<= 1){
		int p = 0;
		for(int i = n - k;i < n;i++) y[p++] = i;
		for(int i = 0;i < n;i++) if(sa[i] >= k) y[p++] = sa[i] - k;
		for(int i = 0;i < m;i++) c[i] = 0;
		for(int i = 0;i < n;i++) c[x[y[i]]]++;
		for(int i = 0;i < m;i++) c[i] += c[i - 1];
		for(int i = n - 1;i >= 0;i--) sa[--c[x[y[i]]]] = y[i];
		swap(x,y);
		p = 1;
		x[sa[0]] = 0;
		for(int i = 1;i < n;i++)
			x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1:p++;
		if(p >= n) break;
		m = p;
	}
}

int rak[maxn],height[maxn];

void getHeight(){
	int k = 0;
	for(int i = 0;i < n;i++) rak[sa[i]] = i;
	for(int i = 0;i < n;i++){
		if(k) k--;
		int j = sa[rak[i] - 1];
		while(s[i + k] == s[j + k]) k++;
		height[rak[i]] = k;
	}
}

bool check(int len){
	int mx = sa[0],mi = sa[0];
	for(int i = 1;i < n;i++){
		if(height[i] >= len - 1) 
			mx = max(sa[i],mx),mi = min(sa[i],mi);
		else 
			mx = mi = sa[i];
		if(mx - mi >= len) return true;
	}
	return false;
}

int solve(){
	int l = 0,r = n,ans = 0;
	while(l <= r) {
		int mid = l + r  >> 1;
		if(check(mid)) l = mid + 1,ans = mid;
		else r = mid - 1;
	}
	return ans;
}

int main(){
	while(~scanf("%d",&n) && n){
		for(int i = 0;i < n;i++) p[i] = readint();
		if(n == 1) {
			puts("0");
			continue;
		}
		for(int i = 0;i < n - 1;i++) s[i] = p[i + 1] - p[i] + 100;
		s[n - 1] = 0;
		build_sa(200);
		getHeight();
		int ans = solve();
		if(ans >= 5) printf("%d
",ans);
		else puts("0");
	}
	
}