KMP(Knuth-Morris-Pratt) 알고리즘, 단일 문자열 패턴 매칭Permalink

위 세 사람이 힘을 합쳐(?) 알고리즘을 고안해냈기에 KMP란 이름이 붙었다.

찾으려는 문자열 $F$가 어떤 문자열 $S$ 안에 있는지 $O(\vert{F}\vert +\lvert{S}\rvert)$에 찾을 수 있는 알고리즘이다.

한 때, Solved.ac 기준 골드 1에 있던 알고리즘이였으나 플레티넘 5로 난이도가 올라버렸다.

충분히 그럴만하고 성질이 처음 접한다면 LCA같은 트리 날먹 플레 알고리즘보다 이해하기에 간단하지 않다(고 개인적으로 생각한다).

KMP의 실패 함수의 정의Permalink

문자열 패턴매칭에서 실패 함수란건 아호-코라식에도 등장하는 개념일 정도로 중요하다.

현재 위치에서 해당 문자가 더 이상 매칭이 될 수 없을 때, 처음부터 다시 검사하는 것이 아닌 가장 될 것 같은 위치로 이동을 하여 검사를 진행하게 만들고, 이것이 알고리즘이 $O(N)$이 되게하는 핵심이다.

KMP에서의 실패함수란 다음과 같다.

$\qquad {\it fail}_{\textstyle i}$ = 문자열 $F$의 $[0, i]$ 범위의 부분 문자열 $F’$ 에서 최대로 일치하는 prefix와 suffix의 길이

단, prefix와 suffix의 길이가 같으면 안된다. 그래서 $\rm fail_0=0$ 인 것이다.

표로 나타내보자.

ABABABDA 라는 문자열이 있다고 하자.

그럼 위와 같이 실패 함수가 만들어진다.

KMP 실패 함수 구현Permalink

코드는 간략하다.

vi kmp_fail(const string &s) {
  vi fail(sz(s));

  for (int i = 1, j = 0; i < sz(s); i++) {
    while (j && s[i] != s[j]) j = fail[j - 1];
    if (s[i] == s[j]) fail[i] = ++j;
  }
 
  return fail;
}

시간복잡도를 먼저 보자면, $i$는 $s$의 길이만큼 돌고, $j$는 한번의 루프에서 최대 1 증가하고 감소하는 while 에 걸려도 0이 되면 while문을 탈출하므로 결국 $O(N)$이 된다.

ABABABDA 를 가지고 얘기를 계속해보자.

코드가 간단하지만 이걸 오랜만에 보거나 처음보면 뭔코드지 싶은데, 조금 자세히 살펴보자.

$i$는 1, $j$는 0부터 시작한다.

일단 처음에 while문은 지나치고 $s_1$과 $s_0$을 비교하는데, 다르므로 $\it fail_1$은 0이 담긴다.

이 비교하는 과정은 이렇게 보고 비교한 것과 같다.

ABABABDA

   ABABABDA

B와 A는 다르다.

ABABABDA

     ABABABDA

$i$ = 2 일 때는 문자가 같으므로 $j$는 1이 되고 $\it fail_2$도 1이 된다.

ABABABDA

     ABABABDA

$i$ = 3 일 때, 또한 같으므로 $j$는 2가되고 $\it fail_3$도 2가 된다.

ABABABDA

     ABABABDA

$i$ = 4 일 때, $j$는 3이되고 $\it fail_4$도 3이 된다.

ABABABDA

     ABABABDA

마찬가지로 $j = \it fail_5 = \rm4$ 이다.

ABABABDA

     ABABABDA

이제 $j$는 while문 조건에 걸린다. $j = \it fail_{\rm 4-1}$ 이 되므로 $\it fail_{\rm 3}$ 인 2가 $j$가 된다.

이 경우를 유심히 살펴보자. $j$가 2가 된 다음 하게될 검사는 다음과 같다.

ABABABDA

          ABABABDA

또 다르므로 $j$는 결국 while문을 돌다 $0$이 되어서 $\it fail_{\rm 6}\rm = 0$이 될 것이다.

그런데 이렇게 $j$가 $\it fail_{\rm \,\,j-1}$ 로 돌아가며

ABABABDA

     ABABABDA

$\qquad \downarrow$

ABABABDA

          ABABABDA

이렇게 검사를 하는 과정을 살펴보면, 처음에는 ABABA의 매칭이 실패했다. 그러면 제일 뒤의 A가 맞지 않는다는건데, 처음으로 돌아가는 것이 아니라 ABA 를 매칭해보려고 시도함을 알 수 있다.

이것이 바로 실패함수와 KMP 알고리즘 전반적으로 걸쳐있는 중요한 성질인데, 어떤 문자를 매칭하려다가 실패를 했을 때,지금까지 일치했었던 부분 문자열에서의 suffix와 일치하는 가장 긴 prefix와의 길이를 알고있다면,

그만큼은 스킵해주고 바로 가장 최적의 위치로 옮겨서 검사를 진행해갈 수 있다는 것이다.

추가 설명 1 - 인덱스 $i$ 와 $j$ 의 의미Permalink

좀더 복잡한 예시와 자세한 설명은 다음과 같다.

일단 코드상에 있는 $i$ 와 $j$ 가 어떤 의미를 갖는지를 살펴볼 필요가 있다.

실패 함수를 만드는 과정은 $S$와 $S$ 자기 자신을 계속 비교하는 문자들의 인덱스를 적절히 변경시키는 과정임을 인지하자.

$i$와 $j$ 모두 $S$ 에서 현재 가리키고 있는 문자 그 자체를 의미한다.

$S$ = ABABDDABAB 라고 해보자.

예를 들어 $i=5,~j=3$ 라고 한다면,

ABABDDABAB $i$
      ABABDDABAB $j$

두 인덱스를 비교하고 있다는 뜻이다. 항상 $i>j$ 이므로 아래쪽 부분이 더 오른쪽으로 가있다고 볼 수 있다.

여기서 $j$ 가 감소한다는 것은 아래쪽 줄이 오른쪽으로 밀린다는 것을 뜻한다. 예를들어 $j=3$ 에서 $j=1$ 로 감소한다는 것은 다음과 같은 결과가 된다.

ABABDDABAB $i$
           ABABDDABAB $j$

추가 설명 2 - 복잡한 예시Permalink

실패함수의 코드를 이해하는 것은 쉽게 혼동이 오는데, 인덱스가 $0-based$ 인가 $1-based$ 인가에 따라 헷갈리기 때문이다.

복잡한 예시를 들어 $0-based$ 로 설명해보겠다.

$S$=AABAACAADAABAABA 라고 하자.

처음에 $i=1,~j=0$ 상태로 시작하므로

AABAACAADAABAABA $i=1$
   AABAACAADAABAABA $j=0$

맞았으므로 $f_1=1$ 이다.

AABAACAADAABAABA $i=2$
   AABAACAADAABAABA $j=1$

틀렸으므로 $j$는 $f_{j-1}=0$ 으로 돌아간다.

AABAACAADAABAABA $i=3$
    AABAACAADAABAABA $j=0$

다시 맞았으므로 $j=1$ 이 된다.

AABAACAADAABAABA $i=4$
    AABAACAADAABAABA $j=1$

또 맞았다. $j=2$ 가 된다.

AABAACAADAABAABA $i=5$
    AABAACAADAABAABA $j=2$

여기서 틀렸으므로 $j=f_{j-1}$이 되고, 이는 $j=1$ 이 되게한다.

그런데 지금까지와 다르게 $j=0$ 으로 변한게 아니다.

이는 다음과 같은 검사를 하게 되었다는 것을 의미한다.

AABAACAADAABAABA $i=5$
    AABAACAADAABAABA $j=1$

왜 이렇게 되었을까?

$S_i$ 와 $S_j$ 가 같은지를 검사하는 시점에 $j$ 의 값은 무엇을 의미할까?Permalink

사실 앞선 설명에서 $j$ 도 그저 $S$ 에서 $S$ 를 검사하고 있을 때 인덱스 중 하나라고 했는데, 이 설명도 맞지만 더 중요한 사실은, $S_i$ 와 $S_j$ 를 비교하고 있는 시점에 $[i-j,\,i-1]$ 와 $[0,\,j-1]$ 이 일치하고 있다는 것이다.

사실 여기까진 당연하다고 생각할 수 있다. 그러나 여기서 실패함수의 정의를 다시 곱씹어보자.

실패함수 $fail$ 을 이용하면 바로 저 $[i-j,\,i-1]=[0,\,j-1]$ 구간에서 최대로 일치하는 prefix와 suffix의 길이를 이용해 그 다음 비교하게 될 자리를 가장 합리적으로 결정할 수 있다는 것이다.

조금 빠르게 진행시켜서 이제 여기를 비교하고 있다고 하자.

현재 $i=14$ 이고 $j=5$ 이다.

AABACAADAABAABA $i=14$
         AABAACAADAABAABA $j=5$

여기서 틀렸는데, 앞에 AABAA이 같음을 볼 수 있다. 근데 여기서 prefix와 suffix에서 같은 부분 중 가장 긴 길이는 $fail_4=2$ 니까 우린 다음과 같이 처음부터 비교를 시작해주는게 아니라

AABACAADAABAABA $i=14$
                       AABAACAADAABAABA $j=0$

다음과 같이 가장 효율적으로

AABACAADAABAABA $i=14$
                  AABAACAADAABAABA $j=2$

검사를 해줄 수 있음을 의미한다.

$f_{5-1}=2$ 니까 다시 $j=f_4=2$ 값으로 돌아왔다.
AABAA 에서 가장 긴 일치하는 prefix와 suffix의 길이가 2이므로 $j$ 를 2로 보내도 문제가 없는 것이다.

왜냐? 0-based에선 j=2 가 곧 두개를 건너뛰고 세 번째 자리부타 검사를 다시 시작하겠다는 것을 의미하니까!

이렇게 $j$ 가 $j=f_{j-1}$ 로 돌아가는 과정은 하나의 $i$ 당 최대 한번만 일어나는것이 아닌 $S_i \ne S_j$ 일 때 $j>0$ 일 때까지 계속해서 반복된다는 사실에 유의하자.

결국 여기선 B가 일치해

이런식으로 테이블이 완성된다.

KMP 구현Permalink

KMP는 구현만 바로 살펴볼건데, 위에서 실패함수가 무엇이고 실패함수가 만들어지는 과정과 실패함수의 쓰임성을 이해했다면 KMP 알고리즘 자체는 거의 똑같게 동작하기 때문이다.

vi kmp(const string &a, const string &b) {
  vi fail = kmp_fail(b), match_indice;
  for (int i = 0, j = 0; i < sz(a); i++) {
    while (j && a[i] != b[j]) j = fail[j - 1];
    if (a[i] == b[j]) {
      if (j == sz(b) - 1) {
        match_indice.push_back(i - sz(b) + 1);
        j = fail[j];
      } else {
        j++;
      }
    }
  }
  return match_indice;
}

시간복잡도는 b의 실패함수를 찾는데 $O(\lvert b \rvert)$, $i$는 $\lvert a \rvert$ 만큼 증가하고 실패함수에서와 같은 이유로 $j$는 한 루프당 최대 1 증가하기 때문에 $O(\lvert a \rvert + \lvert b \rvert)$ 이다.

a에서 b가 있는지 찾고 싶은 것이고, 일단 b의 실패 함수를 만든다.

이후 a의 인덱스 $i$와 b의 인덱스 $j$를 0부터 시작해서 실패함수 생성과 코드가 유사하다.

원리도 똑같다.

여기서 왜 $j$가 |b| - 1 이 되었을 때(일치하는 문자열을 찾았을 때), $j = \it{fail}_{\,j}$ 가 되는지만 짚고넘어가자.

ABCDABCDABCDABCD

    ABCDABCD

요렇게 찾아졌다고 하자. 그럼 지금 $j=7$일 것이다. ${\it fail}_7 = 4$ 일 것이므로 이제 그 다음 비교는 다음과 같이 비교하는 것이 된다.

ABCDABCDABCDABCD

              ABCDABCD

실패함수를 만들때 봤던 것처럼 b 자기 자신의 가장 긴 prefix, suffix가 동일한 것의 길이를 알기 때문에 그만큼(4) skip 하고 비교를 시작할 수 있는 것이다.

이 때, $j$를 무조건 ${\it fail}_j$ 로 만들어야 KMP가 제대로 동작함에 유의하자.
$j$를 0으로 만들거나 하면 알고리즘이 제대로 동작하지 않아 정답을 구할 수 없고 시간복잡도도 보장될 수 없다.

KMP 실패함수의 성질들 ⭐️Permalink

위와 같은 내용을 알면 KMP 기본 문제들을 날먹날먹 할 수 있지만, 응용 문제는 실패함수의 성질을 묻는 문제들도 있다.

실패함수의 성질을 공부하면서 개인적으로 정말 신기했다.

아래부터 글들이 1-based 로 작성되어 있는데, 구현을 한다면 필요에 따라 0-based 로 적절히 인덱스 조절을 해주도록 하자.

실패함수의 성질 1 - Prefix 이면서 동시에 Suffix인 것들의 길이는Permalink

$\it fail_N$

$\it fail_{fail_N}$

$\it fail_{fail_{fail_N}}$

$\it fail_{fail_{fail_{fail_N}}}$

$\cdots$

$\it fail_N$, $\it fail_{fail_N}~\cdots$ 을 반복하면 prefix에도 있고 suffix에도 있는 문자열들을 모두 순회할 수 있다.

이게 어떻게 가능한것일까?

일단 $\it fail_N$ 부터 시작해야한다. 왜냐면 온전한 문자열을 이용해 계산을 한 것은 $\it fail_N$ 밖에 없기 때문이다.

$\it fail_N$ 의 길이가 $T$ 라고 해보자.

원 문자열에서 $[1, T] = [N - a + 1, N]$ 은 동일할 것이다.

예를 들어보자.

위와 같이 인덱스와 실패 함수가 정해지는데, ${\it fail}_9 = 6$ 이다.

그렇다면 $[1, 6]$과 $[4, 9]$ 가 일치함을 알 수 있고, 그 다음 prefix와 suffix가 같은 문자열은 $[1, 6]$ 안에서 있을 것임을 알 수 있다.

왜냐하면 $[1, 6]$ 그 자체로 prefix 이며 suffix이기 때문에 그 다음으로 짧은 동일한 prefix와 suffix도 $[1, 6]$ 에서 찾을 수 있다.

그리고 그 값은 바로 $\mathit{fail}_6 = 3$ 이다.

$[1, 6]$ 그 자체로 실제 문자열의 prefix, suffix와 동일해서, $[1, 6]$ 을 이용해 $\it fail$ 함수를 구한 값이 실제 문자열에서도 prefix와 suffix를 의미한다.

실패함수의 성질 2 - “$L$ 길이의 반복되는 패턴이 나오고 있다” 와 $L = i - \mathit{fail}_i$ 는 동치이다.Permalink

이게 뭔소린가 싶었는데, abcdefabcdzz 라는 문자열을 보자.

$i = 9$ 을 보자.

$L = 9 - 3$

즉, $L = 6$ 이다.

실제로 문자열에서 6자리의 패턴이 $i = 1$ 부터 반복되기 시작하는가?

그렇다. abcdef 가 반복되고있다.

실제로 abcdef 가 반복되지 않는다는 것을 알 수 있지만, $i = 9$ 인 시점에서는 abcdef + abc 이므로 그것이 “나오고 있다” 라고 표현한 것이다.

왜 이게 가능할까?

${\it fail}_n = T$ 라고 해보자.

역시나 $[1, T]$ 와 $[n - T + 1, n]$ 은 같다.

케이스를 나눠보자.

• $2T = n$ 인경우

그러면 딱 절반으로 나뉘는 경우이므로, 패턴이 당연히 존재한다.

• $2T \lt n$ 인경우

abczabc 의 예시를 보자.

$i = 7$ 을보면,

앞에 3개와 뒤에 3개가 같고,

뒤에 3개를 제외한 abcz 가 패턴이 반복되고 있다. 그러므로 이 경우 $L = 7 - fail[7] = 4$ 짜리 패턴이 반복되고 있다.

• $2T > n$ 인 경우

$i = 9$ 를보면, $\mathit{fail}_9=6$이다.

그러면 $9 - 6 = 3$ 짜리의 패턴이 존재할 가능성이 있다 라고 판단이 된다.

$[4, 6]$이 $[1,3]$과 $[7,9]$의 $k$번 반복된 꼴임을 어떻게 알까?

$[1, 3] = A, \,[4, 6] = B,\, [7, 9] = C$ 라고 하자.

$A = C$ 임을 알고있다.

또한 실패 함수의 정의에 의해 $A + B = B + C$ 이다.

즉, $A + B = B + A$ 가 된다.

우리의 결과대로라면 $A$와 $B$가 교환 법칙이 성립함을 알 수 있는데,

$B$가 $A$의 $k$배 꼴이라는 것은 $A$와 $B$의 교환법칙이 성립한다의 충분조건이기 때문에

문자열끼리의 교환 법칙 성립하기 위한 필요 충분 조건은 $A$와 $B$가 동일한 문자열의 $k$배 여야 한다는 것을 다음과 같은 사이트에서 알 수 있었다.

또한 3번째 항목을 보면 $B$는 무조건 $kA\, \footnotesize (k \ge 1)$ 여야 한다.

린던 슈텐베르크 정리에 의해 이러한 일반화를 보일 수 있다고 한다.

${\it fail}_i = 0$ 인 경우에도 이 정리는 성립한다.

아직 하나의 반복도 되지않은 패턴이 이어지고 있다고 생각할 수 있기 때문이다.

문제 풀이: BOJ 16229 - 반복 패턴Permalink

그리고 다음과 같은 문제를 풀어보자.

BOJ 16229 - 반복 패턴

void solve() {
  ...
  int i = fail[n - 1], ans = 0;
  while (i) {
    int pattern_len = n - i;
    int times = (n + k) / pattern_len;
    if (times >= 2 && pattern_len * times >= n) {
      ans = max(ans, pattern_len);
    }
    i = fail[i - 1];
  }
  cout << ans;
}

0-base $\it fail$ 함수이므로 $\it fail$ 배열의 인자에 -1 들이 들어가있다.

위에서 설명한 것과 같이, 패턴이 반복되는 길이를 나누기 연산을 통해 구하고, 이 횟수가 2번 이상이고 실제 문자열보다 긴 경우에 답을 갱신해줄 수 있다.