HihoCoder - 1407 后缀数组二·重复旋律2

oi-forever 2018-06-08 原文

时间限制:5000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。

旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？

解题方法提示

输入

第一行一个整数 N。1≤N≤100000

接下来有 N 个整数，表示每个音的数字。1≤数字≤1000

输出

一行一个整数，表示答案。

样例输入
8
1 2 3 2 3 2 3 1


样例输出
2


总结：后缀数组 + 二分
首先二分长度，check的时候讲连续的height数组大于mid的分成一组
然后求出这一组中最小的后缀起始位置，和最大的后缀起始位置，如果>= mid说明存在不重复的

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 +7;
int sa[maxn], k, p, ln, m, n, a[maxn], rk[maxn];
int y[maxn], H[maxn], wr[maxn], c[maxn];

void SA(int x) {
	m = x;
	for (int i = 1; i <= n; ++i) c[rk[i]]++;
	for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
	for (int i = n; i >= 1; --i) sa[c[rk[i]]--] = i;
	ln = 1; p = 0;
	while(p < n) {
		k = 0;
		for (int i = n - ln + 1; i <= n; ++i) y[++k] = i;
		for (int i = 1; i <= n; ++i) if(sa[i] > ln) y[++k] = sa[i] - ln;
		memset(c, 0, sizeof c);
		for (int i = 1; i <= n; ++i) wr[i] = rk[i];
		for (int i = 1; i <= n; ++i) c[wr[y[i]]]++;
		for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
		for (int i = n; i >= 1; --i) sa[c[wr[y[i]]]--] = y[i];
		for (int i = 1; i <= n; ++i) wr[i] = rk[i];
		p = 1; rk[sa[1]] = 1;
		for (int i = 2; i <= n; ++i) {
			if(!(wr[sa[i]] == wr[sa[i - 1]] && wr[sa[i] + ln] == wr[sa[i - 1] + ln])) ++p;
			rk[sa[i]] = p;
		} ln <<= 1; m = p;
	}
}
void GH() {
	k = 0;
	for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
	for (int i = 1; i <= n; ++i) {
		if(k) --k; int j = sa[rk[i] - 1];
		while(a[i + k] == a[j + k]) ++k;
		H[rk[i]] = k;
	}
}
bool check(int x) {
	int minx = 1e8, maxx = 0;
	for (int i = 1; i <= n; ++i) {
		if(H[i] >= x) {
			minx = min(minx, sa[i]);
			maxx = max(maxx, sa[i]);
			if(maxx - minx >= x) return 1;
		} else minx = maxx = sa[i];
	} return 0;
}
int main() {
	scanf("%d", &n); 
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), rk[i] = a[i];
	SA(1005); GH();
    int l = 2, r = 100000, ans = 0;
    while(l <= r) {
    	int mid = (l + r) >> 1;
    	if(check(mid)) {
    		ans = mid; l = mid + 1;
    	} else r = mid - 1;
    } printf("%d\n", ans);
	return 0;
}