KMP 란?
Knuth, Morris, Pratt 의 앞자를 따서 만든 문자열 검색 알고리즘입니다.
문자열 검색 알고리즘
일반적인 워드 작업이나 웹 페이지를 검색할 때 control + F 기능을 사용해 본 적이 있으실 겁니다.
위와 같이 문자열을 검색 할 때 종종 사용하는 알고리즘 중 하나가 KMP 알고리즘입니다.
그렇다면 KMP알고리즘은 어떤식으로 작동하는 것일까요? 🤔
문자열 검색 알고리즘의 정수
KMP를 알아보기 전에 문자열 검색 알고리즘이 어떤 동향으로 개발되는지를 알아봅시다.
우선 우리가 문자열을 검색하기 위해서는 어떤 방식을 취해야 할까요?
바로 기존의 주어진 문장(TEXT)에서 찾고자 하는 문장(PATTERN)을 비교해나가며 찾는 것입니다. 간단한 예시를 들어보도록 하죠!
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Text | A | B | C | D | A | B | C | D | A | B |
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D | |||||||
| Pattern | A | B | D |
가장 간단한 방법 중 하나로 그냥 무작정 하나씩 비교해보는 것 입니다. 한문자 한문자씩 비교해가며 수행하다보니 보기에도 상당히 비 효율적이라는 것을 알 수 있습니다.
여기서 생각하게 된 것이 어떻게 하면 보다 빠르게 문자열을 탐색할 수 있느냐는 것 입니다.
즉, 우리는 앞서 탐색한 기록을 바탕으로 불필요한 매칭을 피하는 것. False Start를 줄이는 것이 제일 중요하다고 생각할 수 있습니다.
이제 본격적으로 KMP에 대해 알아보도록 하죠!
접두사와 접미사
우선 접두사(Prefix)와 접미사(Suffix)를 알아야 합니다.
접두사는 어근의 앞에 붙는 말, 접미사는 어근의 뒤에 붙는 말을 의미합니다.
예시를 들어 알아보도록 합시다.
위의 banana라는 단어를 예시로 들어보자면 b부터 시작하여 ba, ban, bana 의 순으로 접두사들이라고 합니다. 반대로 접미사의 경우에는 a, na, ana, nana 순으로 접미사들이라고 합니다.
NEXT 배열
KMP알고리즘의 중요한 핵심이 되는 배열인 NEXT배열에 대해 알아보도록 합시다.
우선 False Start를 줄이는 문자열 탐색 알고리즘을 만드는 과정에서 한가지 들 수 있는 생각이 바로 "앞의 일부분의 패턴을 기억하면 어떨까?" 하는 사고입니다. NEXT배열은 위의 사고과정에서 탄생된 배열이라고 생각하면 편합니다.
만들어 지는 과정을 한번 살펴보도록 할까요?
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| NEXT | ||||||||
| PATTERN | A | B | C | D | A | B | A | C |
우선 위와 같은 "ABCDABAC"라는 패턴이 있다고 가정해봅시다. 그럼 NEXT배열의 경우 다음과 같은 과정을 거쳐 만들어지게 됩니다.
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | |
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | |
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | ||
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||
|---|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | 0 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | |||
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | 0 | 1 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | ||||
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | 0 | 1 | 2 | ||||||
| PATTERN | A | B | C | D | A | B | A | C | ||||
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | 0 | 1 | 2 | 1 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | ||||||
| PATTERN | A | B | C | D | A | B | A | C |
| INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NEXT | 0 | 0 | 0 | 0 | 1 | 2 | 1 | 0 | |||||||
| PATTERN | A | B | C | D | A | B | A | C | |||||||
| PATTERN | A | B | C | D | A | B | A | C |
이렇게 만들어지게 된 NEXT배열은 직관적으로 무엇을 의미하는 것일까요? 바로 불일치가 발생했을 시 이동하게될 Pattern의 index입니다!
만일 INDEX 5에 위치한 문자 B에서 불일치가 발생했다고 가정해봅시다. 여기서 불일치가 발생했다면 다음 비교하게 될 INDEX는 불일치가 발생한 INDEX에서 1을 제외한 INDEX에 위치한 NEXT배열의 원소를 갖게 됩니다.
말이 많이 어렵습니다 간단하게 표현해보자면 다음과 같습니다.
if (PATTERN[i] != PATTERN[j]) {
j = NEXT[j-1] // 불일치가 발생한 index-1을 index로 갖는 NEXT의 VALUE
}즉, 5에서 불일치가 발생했으므로 NEXT[5-1]이 가르키는 원소인 1을 다음 INDEX로 갖도록 하는 것 입니다. 위와 같은 과정이라면 우리는 INDEX에 위치한 B를 다음 INDEX로 지정할 것입니다.
여기서 알 수 있는 점은 NEXT배열을 통해 B앞의 A가 일치했었다 사실을 기억했다는 것입니다. 즉 우리는 False Start를 줄일 수 있었습니다.
KMP는 위와같이 동작합니다.
KMP
KMP알고리즘 자체는 NEXT배열을 생성하는 알고리즘과 매우 유사합니다.
우선 NEXT배열을 생성한 이후 PATTERN과 TEXT를 비교해가며 불일치 발생 시 미리 만들어 두었던 NEXT배열을 통해 False Start를 최대한 출여나가며 String을 탐색해 나가는 것입니다.
다음으로 직접 구현한 KMP알고리즘을 보여드리며 마치도록 하겠습니다.
C++로 구현했습니다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int Next[1000001];
string text, pattern;
void INIT(){
getline(cin, text);
getline(cin, pattern);
}
void initNext(){
int j=0;
for(int i=1; i<=pattern.size(); i++){
while (j>0 && pattern[i] != pattern[j]){
j = Next[j-1];
}
if(pattern[i] == pattern[j]){
j++;
}
Next[i] = j;
}
for(int i=0; i<pattern.size(); i++){
cout << Next[i] << " ";
}
cout << "\n";
}
void KMP(){
int j=0;
for(int i=0; i<text.size(); i++){
while (j>0 && text[i] != pattern[j]){
j = Next[j-1];
}
if(text[i] == pattern[j]){
j++;
if(j==pattern.size()){
cout << "패턴이 발생한 위치 : " << i-pattern.size()+1 << '\n';
j = Next[j-1];
}
}
}
cout << "탐색 종료\n";
}
int main(){
INIT();
initNext();
KMP();
return 0;
}또한 Baekjoon Online Judge KMP 알고리즘을 구현해 볼 수 있는 좋은 문제들도 있으니 확인해보시기 바랍니다!
