KMP 알고리즘

KMP Algorithm

미리 알아야할 개념

• 접두사(prefix)

AABAABAC의 접두사: A / AA / AAB / AABA / AABAA / AABAAB / AABAABA / AABAABAC

• 접미사(suffix)

AABAABAC의 접미사: C / AC / BAC / ABAC / AABAC / BAABAC / ABAABAC / AABAABAC

• pi 배열

부분 문자열 중에서 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[0] = 0 → A의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[1] = 1 → AA의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[2] = 0 → AAB의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[3] = 1 → AABA의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[4] = 2 → AABAA의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[5] = 3 → AABAAB의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[6] = 4 → AABAABA의 접두사도 되고 접미사도 되는 문자열의 최대 길이

pi[7] = 0 → AABAABAC의 접두사도 되고 접미사도 되는 문자열의 최대 길이

KMP 알고리즘의 원리

KMP 알고리즘은 검색 과정에서 얻는 정보를 버리지 않고 활용해서 시간을 절약한다. 즉, 불일치가 일어났을 때 지금까지 일치한 글자의 수를 이용해 시도해야할 시작 위치를 빠르게 찾아낸다.

// 예를 들어 ABCAABAABACAABC(텍스트)에서 AABAABAC(패턴)가 어디에 있는지 찾는다고 가정해보자.

// 보통 하나하나 탐색한다고 하면 이런 식으로 풀이가 진행될 것이다.
A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
A | A | B | A | A | B | A | C

A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
    A | A | B | A | A | B | A | C

A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
        A | A | B | A | A | B | A | C

A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
            A | A | B | A | A | B | A | C

위와 같은 풀이에서 텍스트의 길이가 N, 패턴의 길이가 M이라고 했을 때 텍스트의 각 인덱스에 대해 패턴을 검색하므로 시간 복잡도는 O(NM)이 된다.

이 풀이에서는 검색을 할 때마다 틀린 부분에 집중하며 검색을 한다.

// KMP 알고리즘을 이용해서 풀면 아래와 같은 탐색을 하면 된다.
A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
A | A | B | A | A | B | A | C

A | B | C | A | A | B | A | A | B | A | C | A | A | B | C |
            A | A | B | A | A | B | A | C

KMP 알고리즘을 이용한다면 위와 같은 풀이로 될 것이고, 시간 복잡도는 O(N+M)이 된다.

이 풀이를 사용해서 얻은 장점은 명확하다. 원래 처럼 인덱스를 하나 하나 옮기며 비교한 것이 아니라 전에 했던 비교를 통해서 알게 된 부분을 활용하고 있다.

첫 번째 검색에서 알게된 사실은 패턴에서 pi[5] = 4라는 것과 텍스트와 패턴의 비교에서 연속하는 AABA가 매치되었다는 것이다. 텍스트와 패턴이 일치하기 위해서는 AABA 접두사부터 시작해야한다. 그리고 텍스트와 패턴이 일치하는 부분에서 AABA가 존재한다. 그러므로 다음 검색부터는 텍스트 기준 3번 째 인덱스부터 검색을 시작해도 좋다.