KMP 알고리즘(Knuth-Morris-Pratt)은 문자열에서 패턴을 찾는 선형 시간 문자열 탐색 알고리즘이다. 불일치 발생 시 이미 비교한 정보를 재활용해 패턴을 건너뛰어 O(n+m) 시간복잡도를 달성한다.
핵심 아이디어: 실패 함수 (Failure Function)
패턴의 접두사(prefix)이면서 접미사(suffix)인 최장 부분 문자열 길이를 사전 계산한다.
패턴: A B C A B D
idx: 0 1 2 3 4 5
fail: 0 0 0 1 2 0
fail[4]=2 → "ABCAB"에서 "AB"가 접두사이자 접미사
→ 불일치 시 2칸 앞으로 돌아가면 됨
구현
python
def build_failure(pattern):
m = len(pattern)
fail = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = fail[j-1]
if pattern[i] == pattern[j]:
j += 1
fail[i] = j
return fail
def kmp(text, pattern):
n, m = len(text), len(pattern)
fail = build_failure(pattern)
result = []
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = fail[j-1] # 실패 함수로 점프
if text[i] == pattern[j]:
j += 1
if j == m:
result.append(i - m + 1) # 패턴 발견
j = fail[j-1]
return result
# 예시
print(kmp("ABCABCABD", "ABCABD")) # [3]
시간/공간 복잡도
| 단계 | 복잡도 |
|---|
| 실패 함수 빌드 | O(m) |
| 텍스트 탐색 | O(n) |
| 전체 | O(n + m) |
| 공간 | O(m) |
단순 완전탐색(O(nm))과 달리 각 문자를 최대 한 번씩만 비교한다.
브루트 포스와 비교
텍스트: ABCABCABD
패턴: ABCABD
브루트 포스:
ABCABCABD
ABCABD → AB 일치 후 C≠A, 처음부터
BCABD → B≠A, ...
총 ~14번 비교
KMP:
ABCABCABD
ABCABD → 5글자 일치 후 C≠D
↓ fail[4]=2, j=2로 이동
CABCABD → C≠A...
총 ~9번 비교
관련 개념
참고문헌
