KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 매칭 문제를 해결하는 효율적인 알고리즘으로, 기존의 브루트 포스 방식이 O(n*m)의 시간 복잡도를 가지는 반면, 패턴 문자열을 전처리하여 next 배열을 생성함으로써 O(n+m)의 시간 복잡도로 최적화합니다(여기서 n은 메인 문자열의 길이, m은 패턴 문자열의 길이). 본 글에서는 핵심 원리를 바탕으로 C++ 코드를 통해 KMP 알고리즘을 설명하며, 특히 "공통 접두사/접미사"를 활용한 next 배열 생성 방식에 초점을 맞춥니다.
1. KMP 알고리즘의 핵심 아이디어
브루트 포스 매칭의 문제점은 문자가 일치하지 않을 때 메인 문자열의 포인터가 시작 위치의 다음으로 되돌아가고, 패턴 문자열의 포인터가 0으로 초기화되어 많은 중복 비교가 발생한다는 점입니다.
KMP의 핵심 최적화는 패턴 문자열의 "가장 긴 동일한 접두사/접미사(Longest Proper Prefix which is also Suffix)" 정보를 활용하여, 문자가 일치하지 않을 때 메인 문자열의 포인터는 움직이지 않고 패턴 문자열의 포인터만 적절한 위치로 조정하여 중복 비교를 피합니다.
간단한 예를 들면, 패턴 문자열 "abaabc"가 어떤 위치에서 매칭에 실패했을 때, 처음부터 다시 매칭을 시작하는 것이 아니라 이미 일치한 부분의 공통 접두사/접미사를 기반으로 최적의 위치로 직접 이동합니다.
2. 핵심 개념: 가장 긴 동일한 접두사/접미사
next 배열을 이해하려면 먼저 "가장 긴 동일한 접두사/접미사"에 대한 이해가 필요합니다.
- 접두사(Prefix): 문자열의 마지막 문자를 포함하지 않는, 첫 번째 문자로 시작하는 모든 부분 문자열 (예: "aba"의 접두사: "a", "ab")
- 접미사(Suffix): 문자열의 첫 번째 문자를 포함하지 않는, 마지막 문자로 끝나는 모든 부분 문자열 (예: "aba"의 접미사: "a", "ba")
- 가장 긴 동일한 접두사/접미사: 접두사와 접미사 중에서 길이가 가장 길고 내용이 동일한 부분 문자열의 길이 (예: "aba"의 가장 긴 동일한 접두사/접미사 길이는 1, 해당 부분 문자열은 "a")
3. C++ 전체 구현 코드
#include <iostream>
#include <string>
using namespace std;
int longestCommonPrefixSuffix(string str);
void buildNextArray(string pattern, int next[]);
int kmpSearch(string text, string pattern, int next[]);
void displayArray(int arr[], int size);
int main() {
string mainStr = "abaacaabcabaabc";
string patStr = "abaabc";
int next[patStr.length()];
buildNextArray(patStr, next);
cout << "패턴 \"" << patStr << "\"의 next 배열: ";
displayArray(next, patStr.length());
int foundPos = kmpSearch(mainStr, patStr, next);
if (foundPos == -1)
printf("텍스트 <%s>에서 패턴 <%s>을(를) 찾을 수 없습니다.\n", mainStr.c_str(), patStr.c_str());
else
printf("매칭 성공!\n%s\n%*s%s\n", mainStr.c_str(), foundPos, "", patStr.c_str());
return 0;
}
int longestCommonPrefixSuffix(string str) {
int lps = 0;
int len = str.length();
for (int i = 1; i < len; i++) {
if (str.substr(0, i) == str.substr(len - i, i))
lps = i;
}
return lps;
}
void buildNextArray(string pattern, int next[]) {
int len = pattern.length();
if (len >= 1) next[0] = -1;
if (len >= 2) next[1] = 0;
for (int i = 2; i < len; i++) {
next[i] = longestCommonPrefixSuffix(pattern.substr(0, i));
}
}
int kmpSearch(string text, string pattern, int next[]) {
int i = 0, j = 0;
int tLen = text.length();
int pLen = pattern.length();
while (i < tLen && j < pLen) {
if (j == -1 || text[i] == pattern[j]) {
i++; j++;
} else {
j = next[j];
}
}
if (j == pLen)
return i - pLen;
else
return -1;
}
void displayArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("<%d> ", arr[i]);
printf("\n");
}
4. 코드 모듈 상세 분석
(1) longestCommonPrefixSuffix 함수 (가장 긴 공통 접두사/접미사 계산)
- 기능: 입력된 문자열의 가장 긴 동일한 접두사/접미사의 길이를 반환합니다.
- 구현 로직: 1부터 문자열 길이 - 1까지 순회하며, 각 길이 i에 대해 접두사(substr(0, i))와 접미사(substr(len - i, i))가 동일한지 비교하여 가장 큰 일치 길이를 기록합니다.
- 예시: "aba" 입력 시 i=1일 때 접두사 "a"와 접미사 "a"가 일치(lps=1), i=2일 때 "ab"와 "ba"가 불일치하므로 최종 1 반환.
(2) buildNextArray 함수 (next 배열 생성)
next 배열의 길이는 패턴 문자열의 길이와 동일하며, 각 위치 next[i]는 패턴 문자열의 처음 i개 문자의 가장 긴 동일한 접두사/접미사 길이를 나타냅니다. 주요 규칙은 다음과 같습니다.
- next[0] = -1: 알고리즘 관례상 첫 번째 문자가 불일치할 경우를 처리하기 위한 값입니다.
- next[1] = 0: 길이가 2인 문자열은 유효한 공통 접두사/접미사가 없습니다.
- i >= 2: longestCommonPrefixSuffix 함수를 호출하여 패턴 문자열의 처음 i개 문자에 대한 가장 긴 공통 접두사/접미사 길이를 계산하고 next[i]에 할당합니다.
- 예시: 패턴 "abaabc"의 next 배열: <-1> <0> <1> <0> <1> <2>
(3) kmpSearch 함수 (핵심 매칭)
- 이중 포인터 순회: i는 메인 문자열, j는 패턴 문자열을 순회합니다.
- 매칭 성공: i++, j++를 수행하여 다음 문자 비교를 계속합니다.
- 매칭 실패: j = next[j]로 패턴 문자열의 포인터를 최적 위치로 이동시키며, i는 증가하지 않습니다.
- 종료 조건: 메인 문자열을 모두 순회했거나 패턴 문자열을 모두 매칭했을 때 종료합니다.
- 반환값: 매칭에 성공하면 시작 위치(i - pLen)를 반환하고, 실패하면 -1을 반환합니다.
(4) 실행 결과 예시
패턴 "abaabc"의 next 배열: <-1> <0> <1> <0> <1> <2>
매칭 성공!
abaacaabcabaabc
abaabc