문제 이해

1701번: Cubeditor KMP 응용 문제 추천해달라고 GPT에게 물어봤더니 알려준 문제다. 가장 긴 반복 문자열을 찾는 문제로, KMP 문자열 매칭 알고리즘 중 preprocessing 부분과 관련이 있어보이는 문제였다.

다음 pseudo-code를 살펴보자.

preprocessing()
{
	j = 1, k = 0, π[1] = 0;
    while (j<=m) {
    	if (k=0 or P[j] = P[k]) then π[++j] = ++k;
        else k = π[k];
    }
}

[쉽게 배우는 알고리즘]에 나오는 KMP preprocessing 알고리즘이다. π[j]은 배열 P의 처음부터 j번째까지 substring에 대한 정보를 담고 있게 된다. 중요한 점은 바로 이 "정보"가 무엇이냐는 건데, 바로 prefix와 suffix를 같게 만드는 최장 길이를 가리키게 된다. (물론 주어진 pseudo-code는 목적이 다르기 때문에 약간의 수정이 필요하다.)

다시 말해, preprocessing을 거치고 나면 주어진 문자열(s)의 반복 문자열중, 하나가 s의 prefix인 case만 탐색하게 된다는 것이다. 따라서 1701번 문제를 풀기 위해서는

int l = s.length();
for (int i=0; i<l; i++) {
	string sub_s = s[i..l];
    preprcessing() for sub_s
}

이런 식으로 s의 substring에 대해 loop을 돌면서 preprocessing을 수행하면 된다.
preprocessing의 시간복잡도가 $O(n)$ 이므로, $O(n^2)$에 해결가능하다. $n=5000$ 이므로 아슬아슬하게 성공한다.

덧붙이는 말

상위권 유저들은 SA + Kasai 조합으로 더 빠르게 해결한 것 같다. 추후 시도해볼 것.