KMP의 실패 전이와 겹치는 일치

단순 탐색은 몇 글자가 일치하다 실패하면 시작 위치를 한 칸 옮겨 처음부터 다시 비교했고, 그래서 이미 읽은 text의 글자를 여러 번 다시 읽었습니다. KMP 알고리즘은 text를 앞에서부터 한 번만 읽고 결코 되돌아가지 않습니다. 실패했을 때 text를 되감는 대신, 앞 글에서 만든 LPS 배열을 보고 "지금까지 일치한 pattern의 길이"만 줄입니다. 1977년 Knuth, Morris, Pratt가 함께 발표해 세 사람의 이름 머리글자를 딴 이 알고리즘은 최악의 경우에도 O(n + m)에 끝납니다. 이 글에서는 KMP 알고리즘을 만들고, 실패했을 때와 전부 일치했을 때 각각 무엇을 하는지, 왜 그것으로 충분한지를 설명합니다.

일치한 길이 하나만 기억한다

KMP 알고리즘은 text의 글자를 하나씩 읽으면서 변수 j 하나를 유지합니다. j는 "지금까지 읽은 text가 pattern의 앞 j글자로 끝난다"는 것을 뜻하는 일치 길이로, 그런 길이 가운데 가장 긴 것입니다. text의 다음 글자가 pattern[j]와 같으면 일치가 한 글자 늘어나므로 j를 1 늘립니다. j가 pattern의 길이 m이 되면 pattern 전체가 일치한 것이므로, 방금 읽은 글자에서 m - 1만큼 앞의 위치를 기록합니다.

글자가 다르면 앞 j글자짜리 일치는 더 늘릴 수 없습니다. 이때 단순 탐색처럼 처음부터 다시 시작할 필요는 없습니다. 방금까지 일치한 text의 마지막 j글자는 pattern의 앞 j글자와 같으므로, 그 안에서 pattern의 앞부분이기도 한 가장 긴 뒷부분, 곧 lps[j - 1]글자는 여전히 일치한 상태입니다. 그래서 j를 lps[j - 1]로 줄이고, 같은 text 글자를 새 pattern[j]와 다시 비교합니다. 이렇게 일치 길이를 줄이는 일을 실패 전이(failure transition)라고 합니다. j가 0이 될 때까지 줄여도 글자가 다르면, 그 글자에서는 아무것도 일치하지 않은 채로 다음 글자로 넘어갑니다.

text ABABABAC에서 pattern ABABAC를 찾는 과정을 따라가 보겠습니다. LPS 배열은 [0, 0, 1, 2, 3, 0]이고, 표의 j는 그 글자를 읽기 전과 읽은 뒤의 일치 길이입니다.

위치 5에서 실패했을 때 방금 일치한 text의 ABABA 가운데 뒤의 ABA는 pattern의 앞 세 글자와 같습니다. 그래서 j를 3으로 줄이면, text를 되돌아가지 않고도 "위치 2부터 시작하는 일치 후보의 앞 세 글자가 이미 맞았다"는 상태에서 이어 갈 수 있습니다. 단순 탐색이라면 위치 1부터 다시 시작해 B, A, B를 다시 읽었을 것입니다. j를 0으로 지우면 위치 2에서 시작하는 진짜 일치를 놓치고, j를 하나만 줄여 4로 두면 ABAB가 text의 끝과 같다는 근거가 없으므로 틀린 일치를 만들 수 있습니다.

전체가 일치한 뒤에도 겹침을 이어 간다

pattern 전체가 일치한 뒤에는 j를 어떻게 할까요? 0으로 지우면 겹치는 일치를 놓칩니다. 일치한 m글자의 뒷부분이 다음 일치의 앞부분이 될 수 있기 때문입니다. 그래서 전체가 일치하면 실패했을 때와 마찬가지로 j를 lps[m - 1]로 줄입니다. text ABABABA에서 pattern ABA(LPS 배열 [0, 0, 1])를 찾으면 다음과 같습니다.

일치한 ABA의 마지막 A가 다음 일치의 첫 A로 다시 쓰여서, 서로 겹치는 세 일치 0, 2, 4를 모두 찾았습니다.

코드로 옮기기

def prefix_function(pattern):
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        lps[i] = j
    return lps


def kmp_matches(text, pattern):
    if not pattern:
        return list(range(len(text) + 1))
    lps = prefix_function(pattern)
    matches, j = [], 0
    for i, character in enumerate(text):
        while j > 0 and character != pattern[j]:
            j = lps[j - 1]
        if character == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = lps[j - 1]
    return matches


print(kmp_matches("ABABABAC", "ABABAC"))
print(kmp_matches("ABABABA", "ABA"))
print(kmp_matches("AAAA", "AA"))
print(kmp_matches("가나다가나", "가나"))
print(kmp_matches("AB", ""))

[2]
[0, 2, 4]
[0, 1, 2]
[0, 3]
[0, 1, 2]

탐색 부분이 LPS 배열을 만드는 prefix_function과 거의 같은 모양이라는 점에 눈여겨볼 만합니다. LPS 배열을 만드는 일은 pattern이 자기 자신 안에서 얼마나 겹치는지 찾는 일이고, 탐색은 pattern이 text와 얼마나 겹치는지 찾는 일이기 때문입니다. 빈 pattern은 pattern[j]를 읽기 전에 처리해, 단순 탐색에서 정한 대로 n + 1곳을 모두 돌려줍니다. Python 문자열은 한글도 글자 하나를 한 칸으로 다루므로 가나다가나에서도 그대로 동작합니다.

직접 만든 탐색 함수는 단순 탐색과 결과를 비교해 검사해 두는 것이 좋습니다. 정렬의 정답 조건·안정성·시간 측정에서 한 것처럼 무작위 입력을 많이 만들어 비교하면, A와 B만으로 된 짧은 문자열로도 겹치는 일치와 실패 전이가 자주 일어나 실수가 잘 드러납니다. 길이 0에서 20인 text와 길이 1에서 5인 pattern 1000쌍으로 비교해 보면 두 함수의 결과가 모두 같습니다.

왜 맞는가

KMP 알고리즘이 맞다는 것은 다음 불변조건으로 설명합니다. text의 i번 글자까지 읽은 뒤, j는 text[0:i + 1]의 접미사이면서 pattern의 진접두사인 문자열 가운데 가장 긴 것의 길이입니다. 전체 일치를 기록한 직후에는 j를 줄였으므로 늘 m보다 작습니다.

새 글자를 읽을 때 새로운 일치 길이의 후보는 "이전까지의 일치 가운데 하나에 새 글자가 이어지는 것"뿐입니다. 이전까지의 일치 길이들은 큰 것부터 j, lps[j - 1], lps[lps[j - 1] - 1], …로 이어지는 사슬에 빠짐없이 들어 있습니다. 앞 글에서 본 것처럼, 가장 긴 일치보다 짧은 일치는 모두 그 가장 긴 일치 안의 겹침이기 때문입니다. 코드는 이 사슬을 긴 것부터 시도해 새 글자가 맞는 첫 길이를 고르므로, 불변조건이 다음 글자에서도 유지됩니다. 그리고 pattern 전체가 일치하는 순간에는 이 가장 긴 일치가 m이 되므로, 일치하는 위치는 하나도 빠짐없이 기록됩니다.

비용

text의 글자마다 j += 1은 많아야 한 번이므로 탐색하는 동안 j는 모두 합해 많아야 n만큼 늘어납니다. 실패 전이와 전체 일치 뒤의 전이는 할 때마다 j를 적어도 1 줄이고, j는 0보다 작아지지 않으므로 전이의 횟수도 모두 합해 n을 넘지 못합니다. 그래서 탐색은 O(n)이고, LPS 배열을 만드는 O(m)을 더하면 전체가 O(n + m)입니다. 공간은 LPS 배열의 O(m)과, 찾은 위치를 담는 리스트의 크기만큼입니다.

단순 탐색이 가장 느렸던 입력에서 비교 횟수를 세어 보면 차이가 분명합니다. A가 1000개인 text에서 A 9개 뒤에 B가 오는 pattern을 찾으면, 단순 탐색은 시작 위치 991곳에서 10글자씩 비교해 9910번을 비교합니다. KMP 알고리즘은 A가 이어지는 동안 j를 9에서 유지하며 글자마다 실패 전이 한 번과 비교 한 번만 하므로 1991번이면 됩니다. pattern이 길수록 이 차이는 더 커집니다.

정리

• KMP 알고리즘은 text를 앞에서부터 한 번만 읽으며, 지금까지 읽은 text의 끝과 일치하는 pattern 앞부분의 가장 긴 길이 j를 유지합니다.
• 다음 글자가 pattern[j]와 같으면 j를 늘리고, 다르면 j를 lps[j - 1]로 줄이는 실패 전이를 하며 같은 글자를 다시 비교합니다. text를 되돌아가 읽지 않습니다.
• j가 pattern 길이가 되면 위치를 기록하고 j를 lps[m - 1]로 줄여, 겹치는 일치도 이어서 찾습니다.
• 일치 길이의 후보는 LPS 사슬에 빠짐없이 들어 있으므로, 사슬을 긴 것부터 시도하면 일치를 놓치지 않습니다.
• j가 늘어난 총량만큼만 줄어들 수 있으므로 탐색은 O(n), 전체는 O(n + m)입니다.

연습 문제

1. 많이 겹치는 일치

text가 AAAAA이고 pattern이 AAA일 때 kmp_matches의 결과와, 각 일치를 기록한 뒤의 j를 구하세요.

2. 전체 일치 뒤에 j를 0으로 지우면

j = lps[j - 1]로 줄이는 대신 전체가 일치할 때마다 j = 0으로 지우면, ABABABA에서 ABA를 찾은 결과는 어떻게 될까요?

3. 실패 전이가 text를 되돌리지 않는다는 것

KMP 알고리즘에서 text의 위치 i는 한 번도 줄어들지 않습니다. 그런데도 ABABABAC에서 위치 2에서 시작하는 일치를 찾을 수 있었던 이유를, 위치 5에서 일어난 일로 설명하세요.

다음 장의 다항식의 계수 배열·덧셈·곱셈에서는 리스트의 위치가 곧 다항식의 차수를 뜻하는 수치 자료를 다룹니다. 롤링 해시에서 구간을 base진법의 수로 본 것도 다항식을 계산한 것이었습니다.