[웰노운] KMP 알고리즘

서론

KMP 알고리즘에 대해 알아보자.

본론

KMP에 대한 좋은 글은 인터넷에 많이 있으니, 핵심만 알아보자.

결국 KMP 알고리즘은 우리가 원하는 패턴 문자열 $P$의 prefix와 suffix의 최대 길이를 어떻게 구해야 되는지가 관건이다.

문자열 $S[0 \dots n-1]$에 대하여 위의 최대 길이를 구해야 한다.

이러한 길이를 구하기 위해서는 DP를 이용해서 Subproblem으로 쪼갤 수 있다.

먼저 Subproblem을 정의한다. 이를 $\pi[i]$라고 한다.

\[\pi[i] = \max\!\bigl\{\,k \mid 0 \le k \le i,\; S[0..k-1] = S[i-k+1..i]\,\bigr\}.\]

그 다음엔 점화식을 얻어야 하는데, 이 점화식이 여러 DP문제의 스타일과 달라서, 좀 난해한 부분이 있다.

우선, $\pi[i]$와 $\pi[i - 1]$의 연관성을 알 수 있을까?

만약 어떠한 문자열 S에 문자 하나를 붙인다고 쳐보자.

그렇다면, 이 문자가 문자열 S의 최대 길이 prefix의 바로 뒷 idx와 일치하는지, 일치하지 않는지 여부로 분기할 수 있다.

일치하는 경우는 단순히 $\pi[i]$의 값을 1 늘려주면 되므로, 간단하다.

반면, 일치하지 않는 경우를 생각해보자.

그렇다면, 이전에서 봤던 최대 길이 prefix 보다 길이가 작은 prefix의 바로 뒷 idx와 비교해보자.

이는 재귀적으로 가면서.. 문자가 하나도 겹치지 않는다면, 0을 리턴할 것이다.

위 내용을 점화식으로 표현하면 되겠는데, 짚고 넘어가야 할 점이있다.

최대 길이 prefix 보다 길이가 작은 prefix를 어떻게 구해야 할까? 이것이 핵심이다.

깊게 생각을 해보면, 결국 $\pi[\pi[i - 1] - 1]$ 형태로 재귀적으로 파고들어갈 수 있음을 알 수 있다.

abacccaba에 b를 붙인다는 예제로, 이를 이해할 수 있다.

점화식 정리

\[\pi[i] = \begin{cases} 0, & i = 0, \\[6pt] \pi[i-1] + 1, & \text{if } S[i] = S\bigl[\pi[i-1]\bigr], \\[6pt] \pi\!\bigl(\,\pi[i-1]-1\bigr), & \pi[i-1] > 0 \text{ and } S[i] \neq S\bigl[\pi[i-1]\bigr], \\[6pt] 0, & \pi[i-1] = 0 \text{ and } S[i] \neq S[0]. \end{cases}\]

3번째 항목이 재귀식의 형태임에 유의하라.

근데 이를 코드로 옮기는 것은 매우 어려워보인다. 어떻게 옮길 수 있을까?

의사 코드

이를 $O(n)$에 구현할 수 있다. 아니, for문이랑 while문이 안에 있는데 왜 $O(n^2)$가 아니고 $O(n)$이라는 의문점이 존재할 것이다.

왜냐하면, for문과 while문을 따로 분리를 해보면, 각각 $O(n)$의 시간복잡도를 가지는 것을 알 수 있다.

좋다. 이제 의사 코드를 작성해보는데, 의사 코드는 두 포인터를 이용해서도 작성할 수 있으나.

두 포인터의 코드는 어렵기도 하고, 우리는 DP를 이용해 열심히 점화식을 구해왔기에! 이를 이용하여 Bottom-up DP를 짜보자.

따라서 최종 코드는 다음과 같다.

for (int i = 1; i < p.size(); i++) {
    int j = pi[i - 1];

    while (j > 0 && p[i] != p[j])
        j = pi[j - 1];

    pi[i] = j + int(p[i] == p[j]);
} // pi

vector<int> ans;
for (int idx = 0, len = 0; idx < t.size(); idx++) {
    while (len > 0 && t[idx] != p[len])
        len = pi[len - 1];

    len += int(t[idx] == p[len]);

    if (len == p.size()) ans.push_back(idx - p.size() + 1); // 1-based idx
}