문자열 매칭 (KMP, 실패 함수, 라빈-카프)
긴 문서 안에서 특정 단어를 찾는 일은 검색 엔진, 코드 에디터의 Ctrl+F, 유전자 서열 분석, 침입 탐지 시스템의 패턴 매칭까지 컴퓨터가 가장 자주 하는 작업 중 하나다. 가장 단순한 방법은 텍스트의 모든 위치에서 패턴을 한 글자씩 맞춰 보는 브루트포스이지만, 최악의 경우 O(N×M)으로 느려진다. 1977년 발표된 KMP(Knuth-Morris-Pratt) 알고리즘은 이 비교를 O(N+M)의 선형 시간으로 끌어내린 최초의 알고리즘이며, 그 비결은 "이미 비교해서 알아낸 정보를 버리지 않는다"는 한 문장에 있다. 본 글은 브루트포스의 비효율, KMP의 실패 함수, 그리고 해시 기반 라빈-카프와의 비교를 세심하게 정리한다(출처: 위키백과 — Knuth–Morris–Pratt algorithm). 제가 학교 알고리즘 수업에서 KMP의 실패 함수를 처음 손으로 그려 본 날, "왜 패턴을 패턴 자기 자신과 비교하지?"라는 의문이 풀리는 순간의 쾌감을 아직도 기억한다.
브루트포스 문자열 매칭의 한계
문자열 매칭의 기본형부터 보자. 텍스트 T(길이 N)에서 패턴 P(길이 M)가 나타나는 모든 위치를 찾는 문제다. 브루트포스는 T의 0번부터 N-M번 위치까지 각각에서 P를 처음부터 맞춰 보고, 한 글자라도 다르면 다음 위치로 넘어가 다시 처음부터 비교한다.
def brute_force(text, pattern):
n, m = len(text), len(pattern)
result = []
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
result.append(i) # i 위치에서 패턴 발견
return result이 방식의 결정적 약점은 불일치가 생기면 지금까지 맞춘 정보를 전부 버리고 텍스트 포인터를 한 칸만 뒤로 물려 다시 시작한다는 점이다. 예컨대 텍스트 AAAAAB에서 패턴 AAAB를 찾을 때, 매 위치마다 앞의 A 세 개를 다시 비교하는 낭비가 발생한다. 최악의 경우 시간복잡도는 O(N×M)이며, DNA 서열처럼 같은 문자가 반복되는 데이터에서 이 최악이 실제로 자주 나타난다.
KMP의 핵심 — 실패 함수
KMP의 통찰은 이렇다. 패턴 안에서 불일치가 일어났을 때, 지금까지 일치한 부분 문자열의 정보를 이용하면 텍스트 포인터를 뒤로 물리지 않고도 패턴 포인터만 적절한 위치로 점프시킬 수 있다. 이를 위해 패턴을 미리 전처리해 만드는 표가 실패 함수(failure function), 또는 부분 일치 테이블(partial match table)이라 불리는 배열이다.
실패 함수 pi[i]는 "패턴의 0번부터 i번까지의 부분 문자열에서, 접두사이면서 동시에 접미사인 가장 긴 문자열의 길이"로 정의된다. 여기서 접두사(prefix)는 문자열의 앞에서 시작하는 부분, 접미사(suffix)는 뒤에서 끝나는 부분을 가리킨다. 이 값이 곧 "불일치가 났을 때 패턴을 어디까지 되돌려도 안전한가"를 알려 준다.
def build_failure(pattern):
m = len(pattern)
pi = [0] * m
j = 0 # 일치한 접두사 길이
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1] # 실패 함수로 점프
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp_search(text, pattern):
pi = build_failure(pattern)
n, m = len(text), len(pattern)
result, j = [], 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = pi[j - 1] # 텍스트는 안 물리고 패턴만 점프
if text[i] == pattern[j]:
j += 1
if j == m:
result.append(i - m + 1)
j = pi[j - 1]
return result여기서 가장 중요한 성질은 텍스트 포인터 i가 절대 뒤로 물러나지 않는다는 점이다. i는 0부터 N-1까지 단조 증가만 하고, 패턴 포인터 j만 실패 함수를 따라 점프한다. 이 덕분에 전체 시간복잡도가 O(N+M)으로 떨어진다(실패 함수 구축 O(M) + 탐색 O(N)). 실패 함수 자체가 패턴을 패턴 자신과 비교해 만들어진다는 점이 처음에는 낯설지만, 이것이 KMP의 모든 효율을 만들어 내는 엔진이다.
라빈-카프와 비교 — 해시 기반 매칭
KMP가 비교 기반이라면, 라빈-카프(Rabin-Karp)는 해시 기반 문자열 매칭이다. 패턴의 해시값을 한 번 계산해 두고, 텍스트의 길이 M짜리 윈도우를 한 칸씩 밀면서 그 부분의 해시값과 비교한다. 핵심은 윈도우를 한 칸 밀 때 해시를 처음부터 다시 계산하지 않고, 빠지는 글자와 들어오는 글자만 반영해 O(1)에 갱신하는 롤링 해시(rolling hash) 기법이다.
| 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 강점 |
|---|---|---|---|
| 브루트포스 | O(N×M) | O(N×M) | 구현 단순 |
| KMP | O(N+M) | O(N+M) | 최악에도 선형 보장 |
| 라빈-카프 | O(N+M) | O(N×M) | 다중 패턴 동시 탐색 유리 |
| 보이어-무어 | O(N/M) 가능 | O(N×M) | 실무에서 가장 빠른 경우 많음 |
라빈-카프는 해시 충돌이 나면 실제 문자 비교로 확인해야 하므로 최악은 O(N×M)으로 나빠지지만, 여러 패턴을 동시에 찾거나 표절 검사처럼 부분 문자열의 해시를 대량 비교할 때 빛을 발한다. 한편 실무 텍스트 검색에서는 의외로 보이어-무어(Boyer-Moore) 계열이 가장 빠른 경우가 많은데, 이는 패턴의 뒤쪽부터 비교해 불일치 시 여러 칸을 한 번에 건너뛰기 때문이다. 실제로 유닉스의 grep이 보이어-무어 변형을 사용한다.
흔한 오해 하나를 짚으면 "KMP가 항상 가장 빠르다"는 통념인데, KMP의 진짜 강점은 평균 속도가 아니라 최악의 경우에도 O(N+M)을 보장한다는 안정성이다. 평균 속도만 보면 보이어-무어가 더 빠른 경우가 흔하다. 시험에서는 KMP의 실패 함수 계산 과정이 단골 출제되고, 실무에서는 표준 라이브러리의 매칭 함수를 쓰되 그 내부 동작을 이해하는 것이 디버깅의 토대가 된다. 솔직히 이 알고리즘은 처음 배울 때 가장 어렵게 느껴지지만, 실패 함수의 정의 한 줄만 정확히 잡으면 나머지는 그 위에 자연스럽게 쌓인다.
메타 디스크립션: 브루트포스 문자열 매칭의 O(N×M) 한계를 O(N+M)으로 끌어내린 KMP 알고리즘의 실패 함수 원리를 코드와 함께 풀어내고, 해시 기반 라빈-카프·보이어-무어와의 시간복잡도 비교까지 입문자 관점에서 세심하게 정리합니다.