[BOJ] 1605 : 반복 부분문자열

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10;

int n, ans;
int suf[MAXN], rev[MAXN];
char str[MAXN];

void cntsort(vector<int>& ord, int m) {
	int i;
	vector<int> cnt(m + 1, 0), tmp(n + 1);

	for (i = 0; i < n; i++) cnt[ord[i]]++;
	for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (i = n; i--;) tmp[--cnt[ord[suf[i]]]] = suf[i];
	for (i = n; i--;) suf[i] = tmp[i];
	cnt.clear(), tmp.clear();
}

void getsuf() {
	int i;
	vector<int> ord(n + 1, 0), tmp(n + 1, 0);

	for (i = 0; i < n; i++) {
		suf[i] = i;
		ord[i] = str[i] - 'a';
	}

	for (int k = 0; (1 << k) < n; k++) {
		int p = (1 << k);

		for (i = 0; i <= n; i++) {
			tmp[i] = ord[i];
			if (i + p < n) ord[i] = ord[i + p];
			else ord[i] = 0;
		}

		cntsort(ord, k ? n : 26);
		for (i = 0; i <= n; i++) swap(tmp[i], ord[i]);
		cntsort(ord, k ? n : 26);

		for (i = 1; i < n; i++) {
			int a = suf[i], b = suf[i - 1];
			if (ord[a] == ord[b] && tmp[a] == tmp[b]) tmp[b] = 0;
			else tmp[b] = 1;
		}
		ord[suf[0]] = 1;
		for (i = 1; i < n; i++) {
			ord[suf[i]] = ord[suf[i - 1]] + tmp[suf[i - 1]];
		}
	}

	for (i = 0; i < n; i++) {
		rev[suf[i]] = i;
	}
}

void getlcp() {
	int i, p = 0;
	for (i = 0; i < n; i++) {
		if (rev[i]) {
			int prv = suf[rev[i] - 1];
			while (str[prv + p] == str[i + p]) p++;
			ans = max(ans, p);
		}
		p = max(p - 1, 0);
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", str);

	getsuf();
	getlcp();

	cout << ans;

	return 0;
}