0x1E KMP
문자열에서 특정 패턴을 찾는 문제는 생각보다 자주 등장한다. 텍스트 에디터의 Ctrl+F, DNA 서열 분석, 네트워크 패킷 검사 등 다양한 곳에서 **패턴 매칭(Pattern Matching)**이 핵심이 된다.
가장 단순한 방법은 텍스트의 모든 위치에서 패턴을 하나씩 비교하는 브루트포스다. 하지만 이 방법은 텍스트 길이가 N, 패턴 길이가 M일 때 최악의 경우 **O(NM)**의 시간이 걸린다. KMP 알고리즘은 이 문제를 **O(N+M)**에 해결한다.
0x00 알고리즘 설명
KMP(Knuth-Morris-Pratt) 알고리즘의 핵심 아이디어는 단순하다. 이미 비교한 정보를 버리지 않는다는 것이다.
브루트포스에서는 매칭에 실패하면 텍스트 포인터를 한 칸만 옮기고 처음부터 다시 비교한다. 하지만 매칭에 실패하기 직전까지 어디까지 일치했는지를 이미 알고 있다. 이 정보를 활용하면 불필요한 비교를 건너뛸 수 있다.
예를 들어, 텍스트 AABABAABAAB에서 패턴 ABAAB를 찾는다고 하자. 중간에 매칭이 실패했을 때, 지금까지 일치한 부분 중 접두사(prefix)와 접미사(suffix)가 같은 최대 길이를 알면, 그 길이만큼은 다시 비교할 필요가 없다. 이 정보를 미리 계산해두는 것이 바로 **실패 함수(Failure Function)**다.
0x01 실패 함수
KMP는 패턴 매칭 문제를 **O(|A|+|B|)**에 해결할 수 있는 알고리즘이다. 여기서 |A|는 텍스트의 길이, |B|는 패턴의 길이를 의미한다. 솔직히 처음 접하면 굉장히 헷갈리는 알고리즘이다.
KMP를 이해하려면 먼저 **실패 함수(Failure Function)**를 알아야 한다. 실패 함수 f[i]는 패턴 문자열의 0번째부터 i번째까지의 부분 문자열에서, 접두사와 접미사가 일치하는 최대 길이를 저장한다. 단, 부분 문자열 전체 길이와 같은 경우는 제외한다.
예를 들어 패턴이 ABAAB라면:
f[0]= 0 (A, 자기 자신 제외)f[1]= 0 (AB, 일치하는 접두사-접미사 없음)f[2]= 1 (ABA, A가 접두사이자 접미사)f[3]= 1 (ABAA, A가 접두사이자 접미사)f[4]= 2 (ABAAB, AB가 접두사이자 접미사)
이 실패 함수를 구하는 코드는 다음과 같다. 두 포인터 i와 j를 사용하는데, i는 현재 비교할 위치, j는 지금까지 일치한 접두사의 길이를 나타낸다. 문자가 불일치하면 j를 f[j-1]로 되돌려 이전에 일치했던 접두사 위치부터 다시 비교한다.
vector<int> failure(string& s){
vector<int> f(s.size());
int j = 0;
for(int i = 1; i < s.size(); i++){
while(j > 0 && s[i] != s[j]) j = f[j-1];
if(s[i] == s[j]) f[i] = ++j;
}
return f;
}while 루프가 핵심이다. 현재 위치에서 문자가 일치하지 않으면, 이전까지 일치한 접두사 중 다시 활용할 수 있는 부분으로 j를 이동시킨다. 이 과정이 실패 함수의 값을 재귀적으로 따라가는 것이다.
0x02 KMP
실패 함수를 이해했다면 KMP 본체는 거의 동일한 구조다. 텍스트 문자열 s를 한 글자씩 순회하면서 패턴 p와 비교한다. 일치하면 패턴 포인터 j를 증가시키고, 불일치하면 실패 함수를 이용해 j를 되돌린다. j가 패턴의 길이와 같아지면 매칭에 성공한 것이다.
아래 코드는 텍스트 s에서 패턴 p가 존재하면 1을, 존재하지 않으면 0을 출력한다.
#include <bits/stdc++.h>
using namespace std;
vector<int> failure(string& s){
vector<int> f(s.size());
int j = 0;
for(int i = 1; i < s.size(); i++){
while(j > 0 && s[i] != s[j]) j = f[j-1];
if(s[i] == s[j]) f[i] = ++j;
}
return f;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
string s, p;
cin >> s >> p;
vector<int>f = failure(p);
int j = 0;
for(int i = 0; i < s.size(); i++){
while(j > 0 && s[i] != p[j]) j = f[j-1];
if(s[i] == p[j]) j++;
if(j == p.size()){
cout << 1;
return 0;
}
}
cout << 0;
}main 함수의 for 루프를 살펴보면, 실패 함수를 구하는 코드와 구조가 거의 동일하다는 것을 알 수 있다. 차이점은 실패 함수에서는 패턴 자기 자신과 비교하지만, KMP 본체에서는 텍스트와 패턴을 비교한다는 것이다. 실패 함수를 구하는 과정 자체가 사실 "패턴을 패턴 자신에 대해 KMP를 돌리는 것"과 같다.
시간 복잡도는 텍스트 순회 O(|A|)와 실패 함수 구성 O(|B|)를 합쳐 **O(|A|+|B|)**이다. 브루트포스의 O(|A|*|B|)와 비교하면 큰 차이다.
문제 풀이
KMP는 단순히 패턴이 존재하는지 여부만 판단하는 것에 그치지 않는다. 약간의 변형으로 패턴이 등장하는 모든 위치를 찾거나, 등장 횟수를 세는 문제에도 활용할 수 있다. 매칭에 성공했을 때 바로 return하지 않고 위치를 기록한 뒤, j = f[j-1]로 되돌려서 탐색을 계속하면 된다.
대표적인 연습 문제로는 BOJ 1786번 "찾기"가 있다. 이 문제는 텍스트에서 패턴이 등장하는 모든 위치를 출력하는 KMP의 정석 문제다.
리뷰
KMP는 처음 보면 실패 함수가 왜 동작하는지 직관적으로 와닿지 않는다. 하지만 "접두사 == 접미사인 최대 길이"라는 개념만 확실히 잡으면, 나머지는 그 값을 재귀적으로 따라가는 것뿐이다. 코드 자체는 짧지만 그 안에 담긴 아이디어가 깊은 알고리즘이다.
출처: 바킹독님의 실전알고리즘 강의