P4341 [BJWC2010]外星联络

oi-forever 2018-06-11 原文

题目描述

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。

虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串，并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于

但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

输入输出格式

输入格式：

输入文件的第一行是一个整数

输出格式：

输出文件的每一行包含一个出现次数大于

输入输出样例

输入样例#1：复制

7
1010101

输出样例#1：复制

说明

对于 100%的数据，满足 $\le N \le 30000≤N≤3000$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
int n; char ch[maxn];
int wr[maxn], rk[maxn], c[maxn], sa[maxn];
int p, k, ln, y[maxn], m, H[maxn];
void SA(int x) {
	m = x;
	for (int i = 1; i <= n; ++i) rk[i] = ch[i];
	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];
		rk[sa[1]] = 1; p = 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;
		} m = p; ln <<= 1;
	}
}
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(ch[i + k] == ch[j + k]) ++k;
		H[rk[i]] = k;
	} 
}
int main() { 
	int mm;
	scanf("%d", &mm); scanf("%s", ch + 1); n = strlen(ch + 1);
	SA(256); GH();
	for (int i = 1; i <= n; ++i) {
		for (int j = H[i] + 1; j <= n - sa[i] + 1; ++j) {
			int l = 0, r;
			for (l = i; l >= 1 && H[l] >= j; --l);
			for (r = i + 1; r <= n && H[r] >= j; ++r);
			if(r - l > 1) printf("%d\n", r - l);
		}
	}
	return 0;
}