[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