[Daily morning study] KMP 알고리즘과 문자열 패턴 매칭
#daily morning study
문자열 패턴 매칭이란?
문자열 패턴 매칭은 긴 텍스트(Text) 안에서 특정 패턴(Pattern)이 등장하는 위치를 찾는 문제다. 예를 들어 텍스트 "ABABCABABD" 안에서 패턴 "ABABD"가 어디 있는지 찾는 것이다.
가장 단순한 방법은 브루트 포스(Brute Force)로, 텍스트의 모든 위치에서 패턴과 한 글자씩 비교하는 것이다. 텍스트 길이를 N, 패턴 길이를 M이라 할 때 시간 복잡도는 O(N × M)이 된다. 패턴과 텍스트가 길어질수록 느려진다.
KMP 알고리즘은 이를 O(N + M)으로 줄여준다.
KMP 알고리즘의 핵심 아이디어
브루트 포스의 문제는 불일치가 발생했을 때 비교 위치를 무조건 한 칸씩 이동하면서 이미 비교한 정보를 버린다는 점이다.
KMP는 이 낭비를 없앤다. 패턴을 텍스트에 비교하다가 불일치가 발생하면, 패턴에서 이미 일치한 부분의 접두사-접미사 정보를 활용해 패턴을 얼마나 건너뛸지 계산한다. 이미 비교한 글자를 다시 비교하지 않아도 된다.
이 정보를 저장하는 것이 실패 함수(Failure Function) 또는 부분 일치 테이블(Partial Match Table, PMT)이다.
실패 함수(Failure Function)
실패 함수 fail[i]는 패턴의 0~i 부분 문자열에서 접두사(prefix)이면서 동시에 접미사(suffix)인 가장 긴 문자열의 길이를 저장한다. (전체 문자열 제외)
패턴 "ABABD"를 예시로 들면:
| 인덱스 | 부분 문자열 | 접두사 = 접미사 | fail 값 |
|---|---|---|---|
| 0 | A | 없음 | 0 |
| 1 | AB | 없음 | 0 |
| 2 | ABA | “A” | 1 |
| 3 | ABAB | “AB” | 2 |
| 4 | ABABD | 없음 | 0 |
불일치가 fail[i] 위치에서 발생했다면, 패턴을 다음 비교 위치로 fail[i-1] 만큼 점프할 수 있다.
실패 함수 구현
def compute_fail(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
j는 현재까지 일치한 접두사의 길이- 불일치 시
fail[j-1]로 되돌아가며 이전 매칭 정보를 재활용
KMP 검색 구현
def kmp_search(text, pattern):
n, m = len(text), len(pattern)
fail = compute_fail(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
동작 예시
텍스트: "ABABCABABD", 패턴: "ABABD"
i=0: A == A → j=1
i=1: B == B → j=2
i=2: A == A → j=3
i=3: B == B → j=4
i=4: C != D → fail[3]=2, j=2
C != B → fail[1]=0, j=0
C != A → 불일치
i=5: A == A → j=1
i=6: B == B → j=2
i=7: A == A → j=3
i=8: B == B → j=4
i=9: D == D → j=5 == m → 패턴 발견! (위치 5)
결과: 인덱스 5에서 패턴 발견.
시간 복잡도 분석
| 단계 | 시간 복잡도 |
|---|---|
| 실패 함수 계산 | O(M) |
| KMP 검색 | O(N) |
| 전체 | O(N + M) |
i와 j 모두 감소하면 다시 증가해야 하므로, 전체 반복 횟수는 N + M을 넘지 않는다.
브루트 포스 vs KMP 비교
| 항목 | 브루트 포스 | KMP |
|---|---|---|
| 시간 복잡도 | O(N × M) | O(N + M) |
| 전처리 필요 | 없음 | 실패 함수 계산 |
| 불일치 처리 | 한 칸씩 이동 | 최대한 건너뜀 |
| 구현 복잡도 | 매우 단순 | 중간 |
N=100만, M=1000이면 브루트 포스는 최대 10억 번 비교하지만 KMP는 약 100만 번만 비교한다.
활용 사례
- 텍스트 에디터 검색 기능: Ctrl+F로 특정 단어 찾기
- grep 명령어: 파일 내 패턴 검색
- DNA 염기 서열 분석: 특정 유전자 서열 탐색
- 침입 탐지 시스템: 네트워크 패킷에서 악성 패턴 탐지
- 컴파일러: 토큰 인식 과정
관련 알고리즘
KMP 외에도 문자열 매칭 알고리즘은 여러 종류가 있다.
| 알고리즘 | 특징 | 시간 복잡도 |
|---|---|---|
| 브루트 포스 | 단순 비교 | O(N × M) |
| KMP | 실패 함수 기반 건너뜀 | O(N + M) |
| Boyer-Moore | 오른쪽에서 왼쪽 비교, 실무에서 가장 빠름 | O(N/M) ~ O(N×M) |
| Rabin-Karp | 해시 기반 비교, 여러 패턴 동시 검색에 유리 | O(N + M) 평균 |
| Aho-Corasick | 여러 패턴 동시 검색 (트라이 + KMP) | O(N + M + Z) |
실무에서는 Boyer-Moore가 가장 빠른 경우가 많고, 여러 패턴을 동시에 찾아야 할 때는 Aho-Corasick을 쓴다.
핵심 정리
- KMP는 브루트 포스의 중복 비교 낭비를 실패 함수로 제거한다.
- 실패 함수
fail[i]는패턴[0..i]의 가장 긴 진짜 접두사 = 접미사 길이다. - 불일치 발생 시 패턴 포인터를 처음이 아닌
fail[j-1]로 이동한다. - 전체 시간 복잡도는 O(N + M)으로 브루트 포스 O(N × M)보다 훨씬 빠르다.
- 코딩 테스트에서 문자열 검색이나 부분 문자열 관련 문제에서 자주 쓰인다.
