· 개발

KMP 실패 함수: 불일치가 나면 패턴은 어디로 돌아가나

KMP 문자열 검색에서 불일치 뒤 패턴의 어느 위치를 다시 비교할지 정하는 f·next 표의 정의와 계산법, 전체가 선형 시간이 되는 이유를 1977년 원 논문과 Princeton 구현으로 정리합니다.

개발알고리즘문자열

텍스트에서 패턴을 찾는 가장 단순한 방법은 텍스트의 모든 시작 위치에서 패턴을 한 글자씩 맞춰 보고, 틀리면 다음 시작 위치로 넘어가는 것입니다. Knuth, Morris, Pratt의 1977년 논문 “Fast Pattern Matching in Strings”는 이 방법이 느려지는 예로 aaaaaaab를 aaaaaaaaaaaaaab에서 찾는 경우를 듭니다. 패턴이 aⁿb이고 텍스트가 a²ⁿb이면 문자 비교가 (n + 1)²번 일어납니다. 논문은 또 하나의 문제를 지적합니다. 틀릴 때마다 텍스트를 뒤로 되돌려 다시 읽어야 해서, 텍스트를 버퍼로 읽어 들이는 프로그램에서는 처리가 번거로워집니다.

KMP 알고리즘은 텍스트를 되돌리지 않습니다. 불일치가 나면 텍스트 포인터는 그대로 두고, 패턴의 어느 위치부터 다시 비교할지만 미리 만든 표에서 읽습니다. 이 글은 그 표가 무엇을 담는지, 어떻게 만드는지, 왜 전체가 선형 시간이 되는지를 다룹니다. 기준은 위 논문(SIAM Journal on Computing 6권 2호, 323–350쪽, 대학이 호스팅한 사본)이고, 자동자(DFA) 형태의 구현은 Princeton의 Algorithms 4판 KMP.java를 봅니다. Boyer–Moore 같은 다른 알고리즘은 비교를 위해 짧게만 언급합니다.

패턴의 현재 위치가 이미 읽은 텍스트를 알려 준다

논문 1절의 예는 패턴 abcabcacab를 텍스트 babcbabcabcaabcabcabcacabc에서 찾습니다. 패턴의 앞 세 글자 abc는 맞았는데 네 번째 글자 a에서 틀렸다고 해 봅시다. 그러면 방금 읽은 텍스트 네 글자는 abcx이고, x는 a가 아닙니다. 이 사실을 알려면 텍스트를 다시 볼 필요가 없습니다. 논문의 표현대로 패턴에서 어디까지 맞았는지가 방금 읽은 글자를 다시 만들어 낼 만큼의 정보를 담고 있기 때문입니다.

이 정보로 판단하면 패턴을 한 칸, 두 칸, 세 칸 옮겨 봐야 소용이 없습니다. 그 위치들에서는 패턴의 첫 글자 a가 텍스트의 b, c, x 중 하나와 맞아야 하는데, 셋 다 a가 아니기 때문입니다. 그래서 패턴을 바로 네 칸 더 옮길 수 있습니다.

일반적으로 말하면 이렇습니다. 패턴의 j번째 글자에서 틀렸다면 텍스트의 최근 j − 1글자는 패턴의 앞 j − 1글자와 같습니다. 이 j − 1글자의 끝부분이 패턴의 앞부분과 겹칠 수 있는 가장 긴 길이를 알면, 그만큼은 이미 맞은 것으로 두고 바로 다음 글자부터 비교하면 됩니다. 이 길이는 텍스트와 무관하게 패턴만으로 정해지므로 미리 계산해 둘 수 있습니다.

f 표: 겹치는 앞부분의 길이

논문은 이 값을 f[j]로 정의합니다(첨자는 1부터 셉니다). f[j]는 pattern[1] … pattern[i − 1]이 pattern[j − i + 1] … pattern[j − 1]과 같은 i 중에서 j보다 작은 가장 큰 값입니다. 풀어 말하면 패턴의 앞 j − 1글자에서, 앞부분이면서 동시에 끝부분인 가장 긴 문자열(자기 자신은 제외)의 길이에 1을 더한 값입니다. i = 1이면 조건이 저절로 성립하므로 j > 1에서는 항상 f[j] ≥ 1이고, 관례로 f[1] = 0입니다. 이 글에서는 이 표를 실패 함수라고 부르겠습니다. 강의나 교재마다 이름과 첨자 규칙이 다르므로, 다른 자료를 볼 때는 0부터 세는지, 길이를 담는지 위치를 담는지부터 확인하는 것이 좋습니다.

불일치가 나면 j를 f[j]로 바꾸고 같은 텍스트 글자를 pattern[f[j]]와 다시 비교합니다. 패턴을 j − f[j]칸 오른쪽으로 옮기는 것과 같습니다. f[j] = 0이 되면 패턴 첫 글자도 이 텍스트 글자와 맞지 않는다는 뜻이므로 패턴 전체를 이 글자 너머로 옮기고 텍스트의 다음 글자로 넘어갑니다.

next 표: 같은 글자로는 돌아가지 않는다

논문이 실제로 매칭에 쓰는 표는 f를 한 단계 다듬은 next입니다. next[j]는 f[j]와 같은 조건에 pattern[i] ≠ pattern[j]를 더한 것으로, 그런 i가 없으면 0입니다. 이유는 간단합니다. 텍스트 글자 x가 pattern[j]와 달라서 불일치가 났는데 pattern[f[j]]가 pattern[j]와 같은 글자라면, x를 pattern[f[j]]와 비교해도 결과는 이미 정해져 있습니다. 논문은 두 표의 관계를 다음과 같이 정리합니다(j > 1).

  • pattern[j] ≠ pattern[f[j]]이면 next[j] = f[j]
  • pattern[j] = pattern[f[j]]이면 next[j] = next[f[j]]

논문에 실린 abcabcacab의 두 표는 다음과 같습니다.

j 1 2 3 4 5 6 7 8 9 10
pattern[j] a b c a b c a c a b
f[j] 0 1 1 1 2 3 4 5 1 2
next[j] 0 1 1 0 1 1 0 5 0 1

앞 절의 예가 j = 4입니다. f[4] = 1이지만 pattern[4]와 pattern[1]이 둘 다 a이므로 next[4] = 0입니다. 텍스트 글자를 pattern[1]과 비교하는 헛걸음 없이 패턴을 그 글자 너머로 보내고, 결과적으로 패턴은 네 칸 움직입니다. j = 8에서는 pattern[8] = c, pattern[5] = b로 서로 다르므로 next[8] = f[8] = 5입니다. 앞 일곱 글자 abcabca 중 끝의 abca 네 글자는 그대로 맞은 것으로 두고 다섯 번째 글자부터 비교합니다. 패턴은 8 − 5 = 3칸 옮겨집니다.

표를 만드는 방법: 패턴을 자기 자신에 맞춰 본다

f[j + 1]을 구하는 일은 패턴을 텍스트로 삼아 패턴을 검색하는 일과 같습니다. 논문은 이를 패턴 사본 두 개를 겹쳐 놓고 위쪽 사본을 오른쪽으로 미는 그림으로 설명합니다. f[j]를 알고 있을 때 pattern[j] = pattern[f[j]]이면 f[j + 1] = f[j] + 1이고, 다르면 지금까지 만든 표를 따라 더 짧은 겹침으로 내려가며 같은 비교를 반복합니다. next는 위의 관계식으로 같은 루프 안에서 바로 계산할 수 있어서, 논문의 프로그램은 f 값을 메모리에 따로 저장하지도 않습니다.

이 계산은 O(m) 시간이 걸립니다(m은 패턴 길이). 논문의 논증은 이렇습니다. 겹침 길이를 나타내는 변수는 0에서 시작해 1씩 m − 1번 늘어나고, 음수가 되지 않습니다. 표를 따라 내려가는 단계는 매번 이 변수를 줄이므로 전부 합쳐도 m − 1번을 넘을 수 없습니다.

Python으로 옮긴 예

아래 코드는 0부터 세는 Python 리스트에 맞게 f 표와 같은 정보를 담도록 쓴 것입니다. border[i]는 패턴의 앞 i + 1글자에서 앞부분이자 끝부분인 가장 긴 문자열(자기 자신 제외)의 길이이고, 논문 표기로는 i가 0부터 m − 2까지일 때 f[i + 2] − 1입니다(마지막 항목 border[m − 1]에 해당하는 열은 j = m에서 끝나는 논문의 f 표에 없습니다). 논문의 next가 아니라 f에 해당하는 표를 쓰고, 첫 번째만이 아니라 모든 출현 위치를 찾습니다. 패턴은 비어 있지 않다고 가정합니다(논문도 m > 0을 가정합니다).

def border_table(p):
    """border[i] = p[:i+1]의 앞부분이자 끝부분인 가장 긴 문자열의 길이(자기 자신 제외)"""
    border = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = border[k - 1]          # 더 짧은 겹침으로 내려간다
        if p[i] == p[k]:
            k += 1
        border[i] = k
    return border


def kmp_search(text, p):
    """p가 나타나는 모든 시작 위치(0부터 셈)를 돌려준다."""
    border = border_table(p)
    hits = []
    k = 0                              # 지금 맞아 있는 패턴 글자 수
    for i, c in enumerate(text):       # i는 앞으로만 간다
        while k > 0 and c != p[k]:
            k = border[k - 1]
        if c == p[k]:
            k += 1
        if k == len(p):
            hits.append(i - len(p) + 1)
            k = border[k - 1]          # 겹치는 다음 출현을 이어서 찾는다
    return hits


print(border_table("abcabcacab"))                          # [0, 0, 0, 1, 2, 3, 4, 0, 1, 2]
print(kmp_search("babcbabcabcaabcabcabcacabc", "abcabcacab"))  # [15]
print(kmp_search("aaaa", "aa"))                            # [0, 1, 2]

border_table은 앞 절의 “패턴을 자기 자신에 맞춰 보는” 계산이고, kmp_search는 같은 루프를 텍스트에 대해 돌립니다. 두 함수의 구조가 거의 같다는 점이 논문이 말하는 핵심입니다. 첫 번째 예의 결과 [15]는 논문 그림에서 패턴이 최종적으로 놓이는 위치입니다. 마지막 예처럼 출현이 겹칠 때는, 출현을 찾은 뒤 k를 0으로 되돌리지 않고 border 값으로 낮추기 때문에 겹친 출현도 모두 찾습니다. 논문 4절은 같은 일을 이렇게 설명합니다. 패턴 끝에 어떤 텍스트 글자와도 맞지 않는 가상의 글자를 붙인 길이 m + 1의 패턴으로 next 표를 만들고, 출현을 찾을 때마다 next[m + 1] 위치에서 매칭을 이어 갑니다.

왜 선형 시간인가

논문은 매칭 단계의 비용을 이렇게 셉니다. 한 단계마다 텍스트 포인터가 한 칸 나아가거나 패턴이 오른쪽으로 움직입니다. 둘 다 n번(텍스트 길이)을 넘게 움직일 수 없으므로, 표를 만든 뒤의 매칭은 많아야 2n단계입니다. 위 코드로 옮기면 while이 한 번 돌 때마다 k가 줄고, k는 텍스트 글자 하나당 최대 1만 늘어나므로 while의 총 반복 횟수는 n을 넘지 않습니다. 표를 만드는 O(m)을 더하면 전체는 O(m + n)입니다. 논문은 이 O 표기의 상수가 알파벳 크기와 무관하다는 점도 강조합니다. 2004년 Princeton 강의 자료의 요약표도 KMP의 최악 비용을 문자 비교 2N번으로, 단순 검색의 최악을 MN번으로 적었습니다.

텍스트를 되돌리지 않는다는 점은 시간 말고도 의미가 있습니다. 논문은 텍스트를 외부 파일에서 읽을 때 내부 메모리가 O(m) 자리만 있으면 된다고 적었습니다. 이미 읽은 텍스트를 보관할 필요가 없기 때문입니다.

next를 쓰는 이유: 한 글자에서 머무는 시간

전체가 선형이라는 결론은 f를 써도 똑같습니다. 논문 5절도 2절의 알고리즘은 next 대신 f를 써도 올바르게 선형 시간에 동작한다고 적었습니다. 차이는 텍스트 글자 하나를 붙잡고 몇 번이나 표를 따라 내려갈 수 있느냐에 있습니다.

논문은 next를 쓰면 텍스트 글자 하나를 읽는 동안 j := next[j]가 연속으로 실행되는 횟수가 많아야 1 + log_φ m이라는 정리를 증명합니다. φ = (1 + √5)/2 ≈ 1.618인 황금비입니다. 이 상한은 더 낮출 수 없습니다. 피보나치 문자열(이 글에서는 s₁ = b, s₂ = a, sₙ = sₙ₋₁sₙ₋₂로 씁니다)이 최악의 경우를 만들고, 논문의 예에서는 길이 21인 s₈ 패턴의 j = 20에서 불일치가 나면 j가 20, 12, 7, 4, 2, 1, 0을 차례로 거칠 수 있습니다.

f를 쓰면 이 정리가 성립하지 않습니다. 논문의 예는 패턴 aᵐ입니다. f[j] = j − 1이므로, 텍스트 aᵐ⁻¹b…와 맞추다가 m번째 글자에서 틀리면 j := f[j]가 m번 실행되고, 같은 텍스트 글자를 패턴 글자와 m − 1번 더 헛되이 비교한 뒤에야 텍스트가 다음 글자로 넘어갑니다. 같은 패턴의 next를 위의 관계식으로 계산하면 모든 j에서 next[j] = 0이므로(이 글의 계산입니다) 한 번에 패턴 전체를 넘깁니다. 위 Python 코드는 f에 해당하는 표를 쓰므로 이 경우에 글자 하나에서 오래 머물 수 있지만, 전체 반복 횟수는 앞 절의 논증대로 여전히 n을 넘지 않습니다. 입력을 실시간으로 받아 글자 사이의 지연이 중요할 때 next가 의미가 있습니다.

자동자로 만든 KMP: Princeton의 KMP.java

Princeton의 Algorithms 4판 웹사이트에 있는 KMP.java는 같은 아이디어를 결정적 유한 자동자(DFA)로 구현합니다. 상태 j는 “패턴의 앞 j글자가 맞아 있다”는 뜻이고, dfa[c][j]는 상태 j에서 글자 c를 읽은 뒤의 상태입니다. 코드를 읽어 보면 만드는 과정은 이렇습니다.

  1. 재시작 상태 X를 0으로 둡니다. 상태 0에서 패턴 첫 글자를 읽으면 상태 1로 갑니다.
  2. j = 1부터 m − 1까지, 불일치 칸은 상태 X의 칸을 그대로 복사하고, 패턴의 j번째 글자(0부터 셈) 칸만 j + 1로 바꿉니다.
  3. X를 “상태 X에서 그 글자를 읽은 뒤의 상태”로 갱신합니다. X는 패턴의 둘째 글자부터 지금 글자까지를 자동자에 넣었을 때 도착하는 상태입니다.

검색은 텍스트 글자마다 j = dfa[c][j]를 한 번 실행하는 루프 하나이고, j가 m이 되면 멈춥니다. 표를 따라 내려가는 안쪽 루프가 없으므로 텍스트 글자 하나에 드는 일이 항상 표 조회 한 번입니다. 대신 표가 알파벳 크기에 비례해 커집니다. 이 파일의 Javadoc은 최악의 경우 시간이 n + mR에 비례하고 추가 공간이 mR에 비례한다고 적었습니다(R은 알파벳 크기). 문자열을 받는 생성자는 R = 256으로 고정합니다. 문자 값을 그대로 배열 첨자로 쓰는 코드이므로, 이 생성자로는 값이 256 이상인 문자가 들어오면 표 범위를 벗어납니다. 무엇을 한 글자로 셀지는 그 자체로 따로 따져야 할 문제이고, 글자 수가 도구마다 다른 이유에서 다뤘습니다.

두 가지 동작도 짚어 둡니다. search()는 첫 번째 출현 위치만 돌려주고, 찾지 못하면 -1이 아니라 텍스트 길이 n을 돌려줍니다. 같은 사이트의 5.3절 페이지는 KMPplus.java라는 개선판이 알파벳 크기와 무관하게 M + N에 비례하는 시간과 공간을 쓴다고 소개합니다. 이 글에서는 그 파일을 열어 보지 않았습니다.

논문 7절의 역사도 이 대비와 이어집니다. Morris는 1969년 여름 CDC 6400용 텍스트 편집기를 만들며 텍스트를 되돌리지 않는 방법을 찾다가 유한 자동자 이론을 모델로 이 알고리즘에 해당하는 방법을 고안했습니다. Knuth는 이와 따로 Cook의 정리를 Chester의 자동자에 적용하는 과정을 따라가다 같은 원리를 끌어냈고, Pratt가 Knuth의 자료구조를 고쳐 실행 시간이 알파벳 크기와 무관해졌습니다. 2004년 Princeton 강의 자료는 이진 알파벳을 예로 들어, 일치하면 항상 다음 상태로 가므로 불일치 때 갈 상태만 저장하면 된다고 설명합니다. 알파벳이 클 때는 같은 텍스트 글자를 두고 next를 여러 번 따라가는 것으로 전이표의 한 칸을 대신합니다.

실제로 더 빠른가

논문은 이 부분에 단서를 답니다. 3절은 2절의 단순한 형태가 현실적인 데이터에서는 단순 검색과 경쟁하기 어려울 것이라고 적었습니다. 단순 검색의 최악은 m × n이지만 그런 경우가 실제로 나올 가능성이 낮기 때문입니다. 알파벳이 크면 부분 일치 자체가 드물어서, 패턴 첫 글자와 틀리는 일반적인 경우를 처리하는 데 단순한 형태는 불필요한 단계를 많이 밟습니다. 논문은 첫 글자를 특별히 처리하고 끝 검사를 줄인 개선판을 제시하며, 이 형태는 대개 단순 검색보다 빠르게 동작할 것이라고 적었습니다. 이 글은 직접 성능을 측정하지 않았습니다. 평균과 최악의 차이가 큰 알고리즘의 다른 예와, 표준 라이브러리가 그 최악을 어떻게 막는지는 퀵 정렬은 언제 O(n²)이 될까에서 다뤘습니다.

같은 논문의 8절은 1976년에 덧붙인 후기로, Boyer와 Moore(그리고 독립적으로 Gosper)가 패턴의 마지막 글자부터 비교해 텍스트를 건너뛰는 방법을 다룹니다. 알파벳이 크면 평균적으로 텍스트 글자를 약 n/m개만 보면 된다고 설명합니다. 여러 패턴을 동시에 찾는 문제는 next 계산을 일반화한 트라이 방식으로 이어지며, 논문은 Aho와 Corasick이 이를 독립적으로 발견했다고 적었습니다.

정리할 때 확인할 것

  • 첨자 규칙: 논문의 f와 next는 1부터 세고 “다음에 비교할 패턴 위치”를 담습니다. 0부터 세는 구현은 보통 “겹치는 길이”를 담으므로 1씩 어긋납니다. 위 코드의 border[i]는 i ≤ m − 2에서 f[i + 2] − 1이고, 마지막 항목 border[m − 1]은 논문의 f 표에 대응하는 칸이 없습니다.
  • f와 next: 둘 다 전체 O(m + n)을 줍니다. 텍스트 글자 하나에서 머무는 횟수를 1 + log_φ m 이하로 묶는 것은 next입니다.
  • 모든 출현: 출현을 찾은 뒤 k를 0이 아니라 표의 값으로 낮춰야 겹치는 출현을 놓치지 않습니다.
  • DFA 구현: 텍스트 글자당 일이 일정한 대신 표가 m × R 크기입니다. algs4의 KMP.java는 R = 256을 기본으로 쓰고, 첫 출현만 찾으며, 없으면 n을 돌려줍니다.
  • 성능: O(m + n)은 최악의 경우에 대한 보장입니다. 평균적인 입력에서 단순 검색보다 빠른지는 구현과 데이터에 달려 있고, 논문 스스로 단순한 형태는 그렇지 않을 수 있다고 적었습니다.

참고한 자료

  • Donald E. Knuth, James H. Morris, Jr., Vaughan R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing 6(2), 323–350쪽, 1977년 6월 (Johns Hopkins 대학 사이트에 올라온 사본)
  • Robert Sedgewick, Kevin Wayne, KMP.java, Algorithms 4판 코드 (파일의 저작권 표기 2002–2025)
  • Robert Sedgewick, Kevin Wayne, 5.3 Substring Search, Algorithms 4판 웹사이트 (페이지의 최종 수정 표기 2017년 12월 21일)
  • Kevin Wayne, String Searching, Princeton COS 226 강의 자료, 2004년 봄

모든 자료는 2026년 10월 16일에 확인했습니다.

블로그로