[Algorithm] KMP, Knuth-Morris-Pratt 알고리즘
한글, 워드 등의 에티터는 물론이고 웹페이지에서도 찾기 기능이 존재합니다. 본인이 원하는 단어나 음절이 있을 시에 이를 빠르게 찾아 줄 수 있는 기능이죠. KMP 는 바로 이 검색을 위한 알고리즘으로서 알고리즘을 만든 인물들, Knuth, Morris, Pratt 세 명의 이름을 따서 지었습니다. 이 알고리즘이 어떻게 동작하는지 함께 알아보도록 합시다.
단순한 문자열 검색
특별한 알고리즘 없이 문자열 검색을 구현한다면 아마 다음과 같이 생각하기 쉽습니다.
두 개의 문자열 P 와 T 에 대하여 문자열 P 가 문자열 T 에 몇 번이나 어느 위치에 있는지를 찾아야하는 문제입니다. 이 때 T의 길이를 n, P의 길이를 m 이라고 하면, 일반적으로 n>=m 이 성립합니다. n<m 이라면 P가 T 안에 존재할 수 없는 건 당연한 사실이죠.
전체 문자열 T 를 ABCDABCDABDE , P 를 ABCDABD 일 때를 예시로 생각해보겠습니다.
T 문자열은 고정시키고 P 문자열을 하나씩 이동시켜면서 일치여부를 확인해줍니다. T의 첫번째 문자에서 부터시작하는 매칭은 마지막에서 실패하였습니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | O | O | O | O | O | O | X |
마찬가지로 한 칸씩 이동하며 매칭을 시도해볼 것이고, 결국 매칭이 성공하는 지점이 존재합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | O | O | O | O | O | O | O |
다음과 같은 방법을 사용한다면 구현은 비교적 쉽지만 시간복잡도가 가장 큰 문제입니다. 시간복잡도가 어떻게 될까요? 각 매칭마다 최대 m 번의 비교가 필요하고 이러한 비교를 n-m+1 번 해줘야합니다. 즉 O(n*m) 의 시간복잡도를 가지게 되죠. 이보다 효율적인 KMP 알고리즘을 알아보도록 합시다.
KMP 알고리즘
결론부터 이야기하자면 이 알고리즘은 O(n+m) 의 시간복잡도를 가집니다.어떻게 이렇게 개선할 수 있을까요? 다시 위에서 봤던 첫번째 에시를 살펴보면
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | O | O | O | O | O | O | X |
index 6에서 일치하지 않았고 우리는 0번째 index에서 시작하면 일치하는 다는 사실을 알게 되어 다음으로 넘어갔습니다. 다시 말하면 0~5 index 까지는 일치하였다는 것이고 이를 이용해서 알고리즘의 성능을 향상할 수 있습니다.
여기서 우리는 중간과정 없이 한 번에 아래 스텝으로 넘어갈 수 있습니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | O | O | O | O | O | O | O |
접미사와 접두사
위 과정을 설명하기 위해서는 접미사와 접두사의 개념이 필요합니다.0~i 까지 문자열 중 접미사와 접두사가 같은 경우의 가장 긴 길이를 우선 구해줍니다.
예를 들어 문자열 ABAABAB 기준으로 각 i 에 대해 값을 구해주면 아래 표와 같습니다.
| i | 부분 문자열 | 접미사와 접두사가 같은 경우 | 최대 길이 |
|---|---|---|---|
| 0 | A | - | 0 |
| 1 | AB | - | 0 |
| 2 | ABA | A | 1 |
| 3 | ABAA | A | 1 |
| 4 | ABAAB | AB | 2 |
| 5 | ABAABA | ABA | 3 |
| 6 | ABAABAB | AB | 2 |
문제에서 주어진 예시에서 현재 일치했던 문자열 ABCDAB 는 다음과 같습니다.
| i | 부분 문자열 | 접미사와 접두사가 같은 경우 | 최대 길이 |
|---|---|---|---|
| 0 | A | - | 0 |
| 1 | AB | - | 0 |
| 2 | ABC | - | 0 |
| 3 | ABCD | - | 0 |
| 4 | ABCDA | A | 1 |
| 5 | ABCDAB | AB | 2 |
최대 길이를 저장하기 위해서 pi 라는 배열을 정의하고 다음 배열에 길이들을 저장합니다.
중간과정
index 0 에서 비교를 하고 1,2,3을 건너 뛴 체 바로 4로 이동하였습니다. 어떻게 건너 뛸 수 있었는지 알아봅시다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | X |
index 1 에서의 두 값이 다르다면 굳이 비교를 해줄 필요가 없습니다. 그리고 우리는 위에서 정의했던 배열 pi 를 통해서 이를 바로 확인할 수 있습니다. 현재 T[1] 값과 P[1] 값이 B로 같다는 사실을 알고 있습니다. 그리고 지금 상황에서는 T[1] 의 값과 P[0] 의 값이 같은지 확인을 해야줘야하고 이는 P[0]과 P[1] 을 비교하는 것과 같습니다. P[0] 과 P[1] 이 같아지기 위한 조건은 무엇일까요? pi[5] 의 값이 5일 경우, 접미사 ABCDA 와 접두사 BCDAB 가 같다는 것을 의미하기에 자연스럽게 P[0] 과 P[1] 가 같아지게 됨을 의미합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | X |
그 다음 단계 역시 마찬가지 방법으로 진행됩니다.이번에는 index 2 를 확인해보겠습니다. 마찬가지로 T[2] 값과 P[2] 값이 같다는 사실은 알고 현 상황은 T[2] 값과 P[0] 값이 같은지 확인을 해줘야합니다. 이는 P[2] 와 P[0] 이 같음을 확인하는 것과 같죠. 따라서 pi[5] = 4 이어야지만 성립하게 됩니다. 따라서 생략하고 넘어갈 수 있죠.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | X |
위와 같은 맥락으로 pi[5] = 3 이어야 하므로 생략합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | C | D | A | B | C | D | A | B | D | E |
| P | A | B | C | D | A | B | D | |||||
| 일치여부 | O | O | O | O | O | O | O |
pi[2] = 2 이기 때문에 T[4], T[5] 가 P[0], P[1] 가 일치한다는 사실을 바로 알 수. 있습니다. 그리고 뒤에 남은 부분은 직접 비교를 해줌으로서 많은 연산을 줄일 수 있습니다.
C++을 통한 KMP 구현
해당 풀이는 백준에 KMP 를 사용하는 문제가 있어서 해당 문제의 답을 코드로 작성해보았습니다.
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> getPi(string p){
int m = (int)p.size(), j=0;
vector<int> pi(m, 0);
for(int i = 1; i< m ; i++){
while(j > 0 && p[i] != p[j])
j = pi[j-1];
if(p[i] == p[j])
pi[i] = ++j;
}
return pi;
}
vector<int> kmp(string s, string p){
vector<int> ans;
auto pi = getPi(p);
int n = (int)s.size(), m = (int)p.size(), j =0;
for(int i = 0 ; i < n ; i++){
while(j>0 && s[i] != p[j])
j = pi[j-1];
if(s[i] == p[j]){
if(j==m-1){
ans.push_back(i-m+1);
j = pi[j];
}else{
j++;
}
}
}
return ans;
}
int main(){
string s, p;
getline(cin, s);
getline(cin, p);
auto matched = kmp(s,p);
printf("%d\n", (int)matched.size());
for(auto i : matched)
printf("%d ", i+1);
return 0;
}
코드는 크게 세 부분으로 나누어지며 pi 배열을 만드는 getPi, KMP 알고리즘을 사용하는 kmp, 그리고 main 함수입니다.
kmp 함수
vector<int> kmp(string s, string p){
vector<int> ans;
auto pi = getPi(p);
int n = (int)s.size(), m = (int)p.size(), j =0;
for(int i = 0 ; i < n ; i++){
while(j>0 && s[i] != p[j])
j = pi[j-1];
if(s[i] == p[j]){
if(j==m-1){
ans.push_back(i-m+1);
j = pi[j];
}else{
j++;
}
}
}
return ans;
}
핵심이 되는 알고리즘은 바로 while 문입니다. pi 배열을 이용해서 필요없는 비교를 생략하는 과정인데 이 역시 예시를 통해 알아보겠습니다.
T : ABABABABBABABABABC , P : ABABABABC
for 문이 돌아서 i = 8 인 상황에 둘이 다르기 때문에 while 이 돌아갑니다.
j = pi[7] (==6) 이기 때문에 다음 시행 시 j 를 앞으로 땡깁니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | A | B | A | B | A | B | B(i) | A | B | A | B | A | B | A | B | C |
| P | A | B | A | B | A | B | A | B | C(j) | |||||||||
| 일치 여부 | O | O | O | O | O | O | O | O | X |
또 일치하지 않으므로 j = pi[6] (==4) 로 이동합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | A | B | A | B | A | B | B(i) | A | B | A | B | A | B | A | B | C |
| P | A | B | A | B | A | B | A(j) | B | C | |||||||||
| 일치 여부 | O | O | O | O | O | O | X |
또 일치하지 않으므로 j = pi[3] (==2) 로 이동합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | A | B | A | B | A | B | B(i) | A | B | A | B | A | B | A | B | C |
| P | A | B | A | B | A(j) | B | A | B | C | |||||||||
| 일치 여부 | O | O | O | O | X |
또 일치하지 않으므로 j = pi[1] (==0) 로 이동합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | A | B | A | B | A | B | B(i) | A | B | A | B | A | B | A | B | C |
| P | A | B | A(j) | B | A | B | A | B | C | |||||||||
| 일치 여부 | O | O | X |
while 문은 종료되고 i 는 다음 수인 9로 , j = 0 값이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | A | B | A | B | A | B | A | B | B | A(i) | B | A | B | A | B | A | B | C |
| P | A(j) | B | A | B | A | B | A | B | C | |||||||||
| 일치 여부 | O | O | O | O | O | O | O | O | O |
getPi 함수
vector<int> getPi(string p){
int m = (int)p.size(), j=0;
vector<int> pi(m, 0);
for(int i = 1; i< m ; i++){
while(j > 0 && p[i] != p[j])
j = pi[j-1];
if(p[i] == p[j])
pi[i] = ++j;
}
return pi;
}
검색 단어는 길이가 짧기 때문에 시간복잡도를 줄이는게 큰 의미는 없지만 KMP 알고리즘을 여기서도 사용하여 O(m) 으로 줄일 수 있습니다.
ABABABAC 를 예시로 pi 배열의 생성 과정을 알아보도록 하겠습니다.
우선 배열은 0의 초기값으로 시작합니다. i 는 P1 의 index 를 j 는 P2 의 index 역할을 하게 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||
| P1 | A | B | A | B | A | B | A | C | |||||||
| P2 | A | B | A | B | A | B | A | C |
i = 1 )
P1[1] 과 P2[0] 을 비교합니다. 둘은 다르기 때문에 접두사와 접미사는 같지 않다고 볼 수 있고 pi[1] = 0 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||||||
| P1 | A | B(i) | A | B | A | B | A | C | |||||||
| P2 | A(j) | B | A | B | A | B | A | C |
i = 2)
P1[2] 과 P2[0] 을 비교합니다. 둘이 같기 때문에 A 는 접두사 이자 접미사가 되고 pi[2] = 1 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |||||||
| P1 | A | B | A(i) | B | A | B | A | C | |||||||
| P2 | A(j) | B | A | B | A | B | A | C |
i = 3 )
P1[3] 과 P2[1] 을 비교합니다. 둘이 같기 때문에 AB 는 접두사 이자 접미사가 되고 pi[3] = 2 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | |||||||
| P1 | A | B | A | B(i) | A | B | A | C | |||||||
| P2 | A | B(j) | A | B | A | B | A | C |
i = 4 )
P1[4] 과 P2[2] 을 비교합니다. 둘이 같기 때문에 ABA 는 접두사 이자 접미사가 되고 pi[4] = 3 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | |||||||
| P1 | A | B | A | B | A(i) | B | A | C | |||||||
| P2 | A | B | A(j) | B | A | B | A | C |
i = 5 )
P1[5] 과 P2[3] 을 비교합니다. 둘이 같기 때문에 ABAB 는 접두사 이자 접미사가 되고 pi[5] = 4 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 0 | |||||||
| P1 | A | B | A | B | A | B(i) | A | C | |||||||
| P2 | A | B | A | B(j) | A | B | A | C |
i = 6 )
P1[6] 과 P2[4] 을 비교합니다. 둘이 같기 때문에 ABABA 는 접두사 이자 접미사가 되고 pi[6] = 5 이 됩니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | |||||||
| P1 | A | B | A | B | A | B | A(i) | C | |||||||
| P2 | A | B | A | B | A(j) | B | A | C |
i = 7 )
P1[7] 과 P2[5] 을 비교합니다. 둘이 다르기 때문에 j = pi[4] (==3) 이 되어 앞으로 당깁니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | |||||||
| P1 | A | B | A | B | A | B | A | C(i) | |||||||
| P2 | A | B | A | B | A | B(j) | A | C |
i = 7 )
i 는 7을 유지하고 while 문을 돌게 됩니다.
P1[7] 과 P2[3] 을 비교합니다. 둘이 다르기 때문에 j = pi[2] (==1) 이 되어 앞으로 당깁니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | |||||||
| P1 | A | B | A | B | A | B | A | C(i) | |||||||
| P2 | A | B | A | B(j) | A | B | A | C |
i = 7 )
i 는 7을 유지하고 while 문을 돌게 됩니다.
P1[7] 과 P2[1] 을 비교합니다. 둘이 다르기 때문에 j = pi[0] (==0) 이 되어 앞으로 당깁니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | |||||||
| P1 | A | B | A | B | A | B | A | C(i) | |||||||
| P2 | A | B(j) | A | B | A | B | A | C |
i = 7 )
i 는 7을 유지하고 while 문을 돌게 됩니다.
P1[7] 과 P2[0] 을 비교합니다. 둘이 다르기 때문에 j 는 이동해야하지만 이미 0이기에 반복문을 종료합니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pi 배열 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 0 | |||||||
| P1 | A | B | A | B | A | B | A | C(i) | |||||||
| P2 | A(j) | B | A | B | A | B | A | C |