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

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

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

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

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

KMP의 실패 함수의 정의

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

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

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

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

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

표로 나타내보자.

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

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

  A B A B A B D A
$\it i$ 0 1 2 3 4 5 6 7
$\it fail_{\,i}$ 0 0 1 2 3 4 0 1

KMP 실패 함수 구현

코드는 간략하다.

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$ 의 의미

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

일단 코드상에 있는 $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 - 복잡한 예시

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

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

$S$=AABAACAADAABAABA 라고 하자.

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

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

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

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1                            

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

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

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1 0                          

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

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

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1 0 1                        

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

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

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1 0 1 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$ 의 값은 무엇을 의미할까?

사실 앞선 설명에서 $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$ 이다.

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1 0 1 2 0 1 2 0 1 2 3 4 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가 일치해

  A A B A A C A A D A A B A A B A
$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
$f$ 0 1 0 1 2 0 1 2 0 1 2 3 4 5 3 4

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

KMP 구현

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 실패함수의 성질들 ⭐️

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

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

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

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

$\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]$ 은 동일할 것이다.

예를 들어보자.

  a b c a b c a b c
$i$ 1 2 3 4 5 6 7 8 9
$\it fail$ 0 0 0 1 2 3 4 5 6

위와 같이 인덱스와 실패 함수가 정해지는데, ${\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$ 는 동치이다.

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

  a b c d e f a b c d z z
$i$ 1 2 3 4 5 6 7 8 9 10 11 12
$\it fail$ 0 0 0 0 0 0 1 2 3 4 0 0

$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 의 예시를 보자.

  a b c z a b c
$i$ 1 2 3 4 5 6 7
$\it fail$ 0 0 0 0 1 2 3

$i = 7$ 을보면,

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

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

  • $2T > n$ 인 경우
  a b c a b c a b c
$i$ 1 2 3 4 5 6 7 8 9
$\it fail$ 0 0 0 1 2 3 4 5 6

$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 - 반복 패턴

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

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번 이상이고 실제 문자열보다 긴 경우에 답을 갱신해줄 수 있다.

Comments

You may also enjoy

Shader, Graphics Animation

열심히 작업했다. 듀오링고식 Stage를 깨가는 UI 같은 느낌인것같다.