BOJ 14959. Slot Machines
문제 해석
\(k\)번째 항부터(초항은 \(0\)번째 항이다) 주기 \(p\)로 반복됨이 알려져 있는 수열의 처음 \(n\)개 항이 주어질 때, 가능한 쌍 \((k, p)\) 중에서 \(k+p\)가 가장 작은 것, 그 중에서 \(p\)가 가장 작은 것을 구해라.
참고로, \(k\)가 \(n\)보다 작다고 가정해도 된다. 원문의 “However, there are many candidates for k and p: one extreme case is k=5 and p=1, and another is k=0 and p=6.”에서 약하게 유추할 수 있지만 명확히 하기 위해 언급해 둔다.
접근
이하, \([i:j]\) 표기를 Python notation처럼 사용한다.
KMP 알고리즘에서 사용하는 실패함수(failure function, prefix function)는 주기열(periodic sequence)과 깊은 관계에 있다(BOJ 4354. 문자열 제곱). 실패함수의 값이 곧 border(prefix도 되고 suffix도 되는 문자열 중에 자기 자신을 제외하고 가장 긴 것)의 길이이기 때문에, 그 길이의 prefix와 suffix를 왔다갔다 하면서 앞에서부터 한 주기씩 채울 수 있다.
예를 들어 길이 \(8\)인 문자열의 border 길이가 \(6\)이라면 \([0:6]\)과 \([2:8]\)이 같아야 하므로 \([0:2]\)와 \([2:4]\)가 같고, 다음으로 \([2:4]\)와 \([4:6]\)이 같고… 이런 식으로 주기가 \(2\)인 \(\mathsf{ABABABAB}\) 꼴의 문자열임을 알 수 있으며, 주기가 \(2\)인 것은 문자열과 border의 길이 차 \(8-6=2\)에서 기인했음을 볼 수 있다. 한편 위에 쓴 것처럼 자기 자신을 제외하고 가장 긴 것 이라는 조건이 border의 정의에 포함되어 있기 때문에 이렇게 구한 주기가 최소라는 것은 자명하다.
특히 문자열이 주기의 배수로 정확히 떨어지지 않을 때도 유효하다는 사실에 주목하자.
- \(\mathsf{ABCDEAB}\)처럼 두 번째 또는 그 이후 주기 도중에 끝나는 경우, 두 번째 주기의 시작부터 border가 되어 주기가 올바르게 구해진다.
- \(\mathsf{ABCD}\)처럼 두 번째 주기가 시작하지 않은 경우, border 길이가 \(0\)이므로 전체 문자열이 주기가 되며 이 성질은 (이 문제를 포함한) 많은 상황에서 편리하다.
저 두 예시를 생각하면 (수열의 길이 - border의 길이)로 계산한 우리의 주기는 본 문제에서 말하는 주기와 일치한다는 걸 알 수 있다.
여기에 아이디어 하나를 더하면 본 문제를 풀 수 있다. 주어진 수열의 모든 suffix의 주기를 알면 다 푼 셈인데, KMP를 \(\mathcal{O}(n)\)번 써야 할 것 같다. 하지만 KMP가 모든 prefix 의 border를 \(\mathcal{O}(n)\)에 구해주고, 주기열을 뒤집어도 같은 주기의 주기열이기 때문에, 수열을 뒤집어서 KMP를 한 번만 쓰면 된다. 뒤집은 수열을 \(0\)부터 index하고 prefix \([:i+1]\)의 border 길이를 \(\mathrm{pf}[i]\)라 하면
\[k_i = n-1-i,\quad p_i = i+1-\mathrm{pf}[i]\]가 \((k, p)\)에 대한 하나의 후보가 된다. 즉, 원본 수열에서 index \(n-1-i\)에서 첫 번째 주기가 시작한다고 했을 때의 \((k, p)\)이다.