핵심 정리
| 항목 | 내용 |
|---|---|
| 목적 | 긴 문자열에서 패턴 위치 찾기 |
| 핵심 배열 | pi[i]: i까지의 문자열에서 같은 접두사/접미사 길이 |
| 시간 | O(N + M) |
| 장점 | 비교 실패 후 처음부터 다시 보지 않음 |
| 자주 쓰는 곳 | 반복 패턴, 문자열 검색, border 계산 |
csharp
int[] pi = BuildPi(pattern);
int matched = 0;구조
KMP는 패턴의 접두사와 접미사가 얼마나 겹치는지 미리 계산합니다. 검색 중 불일치가 나면, 이미 맞은 부분을 버리지 않고 다음으로 가능한 접두사 길이로 이동합니다.
text
pattern: a b a b a c
pi: 0 0 1 2 3 0pi[i]는 pattern[0..i]에서 접두사이면서 접미사인 가장 긴 길이입니다. 자기 자신 전체는 제외합니다.
csharp
int[] BuildPi(string pattern)
{
int[] pi = new int[pattern.Length];
int j = 0;
for (int i = 1; i < pattern.Length; i++)
{
while (j > 0 && pattern[i] != pattern[j])
{
j = pi[j - 1];
}
if (pattern[i] == pattern[j])
{
pi[i] = ++j;
}
}
return pi;
}검색도 같은 원리입니다. matched가 패턴 길이에 도달하면 매칭 위치를 기록하고, 겹치는 다음 매칭을 위해 pi[matched - 1]로 되돌립니다.
검색 흐름
csharp
List<int> Search(string text, string pattern)
{
int[] pi = BuildPi(pattern);
var found = new List<int>();
int matched = 0;
for (int i = 0; i < text.Length; i++)
{
while (matched > 0 && text[i] != pattern[matched])
{
matched = pi[matched - 1];
}
if (text[i] != pattern[matched]) continue;
matched++;
if (matched == pattern.Length)
{
found.Add(i - pattern.Length + 1);
matched = pi[matched - 1];
}
}
return found;
}pattern[matched]를 읽기 전에 pattern이 빈 문자열인지 별도 처리해야 합니다. 코딩 테스트에서는 보통 패턴 길이가 1 이상으로 주어지지만, 일반 함수라면 경계 조건을 먼저 정합니다.
주의할 점
실패했을 때 matched--처럼 한 칸만 줄이면 KMP의 장점이 사라집니다. 반드시 pi[matched - 1]로 이동해 이미 계산한 border 정보를 써야 합니다.
매칭을 하나 찾은 뒤 matched = 0으로 초기화하면 겹치는 패턴을 놓칠 수 있습니다. 예를 들어 aaaaa에서 aaa를 찾는 경우 시작 위치 0, 1, 2를 모두 찾아야 할 수 있습니다.
참고 링크
1 sources