【POJ 3261】Milk Patterns 可重叠的k次最长重复子串

时间：2023-03-09 08:41:11
【POJ 3261】Milk Patterns 可重叠的k次最长重复子串

可重叠的k次最长重复子串

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 21003;

int t1[N], t2[N], c[N];

void st(int *x, int *y, int *sa, int n, int m) {

	int i;

	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];

}

void mkhz(int *r, int *sa, int n, int m) {

	int *x, *y, *t, i, j, p;

	x = t1; y = t2;

	for(i = 0; i < n; ++i) x[i] = r[i], y[i] = i;

	st(x, y, sa, n, m);

	for(j = 1, p = 1; p < n; j <<= 1, m = p) {

		for(p = 0, i = n - j; i < n; ++i) y[p++] = i;

		for(i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

		st(x, y, sa, n, m);

		for(t = x, x = y, y = t, x[sa[0]] = 0, p = 1, i = 1; i < n; ++i)

			x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j] ? p - 1 : p++;

	}

}

void mkh(int *a, int *sa, int *rank, int *h, int n) {

	int k = 0, i, j;

	for(i = 1; i <= n; ++i) rank[sa[i]] = i;

	for(i = 1; i <= n; h[rank[i++]] = k)

		for(k ? --k : 0, j = sa[rank[i] - 1]; a[i + k] == a[j + k]; ++k);

}

int sa[N], rank[N], h[N], n, a[N], b[N], key;

bool can(int k) {

	int ret = 1;

	for(int i = 2; i <= n; ++i)

		if (h[i] >= k) {

			++ret;

			if (ret >= key) return 1;

		}

		else ret = 1;

	return ret >= key;

}

int H[1000003];

int main() {

	scanf("%d%d", &n, &key);

	for(int i = 1; i <= n; ++i)

		scanf("%d", &a[i]), b[i] = a[i];

	sort(b + 1, b + n + 1);

	int tot = unique(b + 1, b + n + 1) - b - 1;

	for(int i = 1; i <= tot; ++i) H[b[i]] = i;

	for(int i = 1; i <= n; ++i) a[i] = H[a[i]];

	mkhz(a, sa, n + 1, 200);

	mkh(a, sa, rank, h, n);

	int left = 0, right = n, mid;

	while (left <= right) {

		mid = (left + right) >> 1;

		if (can(mid)) left = mid + 1;

		else right = mid - 1;

	}

	printf("%d\n", left - 1);

	return 0;

}

离散化学的别人的，，，好应付的离散化

相关文章