[Algorithm] KMP 알고리즘 (Knuth-Morris-Pratt algorithm)

---

KMP 알고리즘 (KMP Algorithm)

 

라빈-카프 알고리즘과 같이 문자열 탐색에서 직선적인 방법(참고링크)의 단점을 극복하기 위한 알고리즘이다. 알고리즘을 고안한 세 사람의 이름을 따서 KMP 알고리즘이라 이름 붙었다.

라빈-카프 알고리즘은 문자열을 숫자로 바꾸고 해싱하는 방법으로 비교횟수를 줄였다면 KMP 알고리즘은 패턴 문자열의 접두부(prefix), 접미부(suffix) 매칭을 통해 불필요한 비교를 제거함으로써 비교횟수를 줄인다.

불필요한 비교라는 것을 알아보기 위해 다음과 같이 텍스트 문자열과 패턴 문자열을 가정해보자.

$$ \text{Text : } T = adcbadeadcbadcbadcf, \qquad \text{Pattern : } P = adcbadcf $$

이제 비교를 해보자. 비교에서 패턴의 가장 처음 달라지는 부분을 빨간색으로 표시하였다.

$$
\begin{aligned}
&adcbadeadcbadcbadcf \\
&adcbad\color{red}{c}f \\
&\,\,\color{red}{a}dcbadcf \\
&\,\,\,\,\color{red}{a}dcbadcf \\
&\,\,\,\,\,\,\color{red}{a}dcbadcf \\
&\,\,\,\,\,\,\,\,ad\color{red}{c}badcf \\
&\qquad\qquad\,\,\cdots \\
&\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, adcbadcf
\end{aligned}
$$

확인해보면 처음 비교할 때 이미 텍스트의 두 번째가 $ d $ 인 것을 알 수 있다. 그런데 다시 이를 패턴의 첫번째와 비교한다. 이것을 줄여 비교횟수를 줄이는 것이다.

이를 줄이기 위해 최대 접두부 테이블(maximun prefix table)을 만든다. 이를 통해 접두-접미사 일치 길이(SP, suffix-prefix)를 계산해놓는다.

 

---

접두-접미사 일치 길이 계산

 

먼저 패턴이 $ acbdacba $ 라 하자. 그렇다면 다음과 같은 테이블을 만든다.

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$
$i$
$SP$	0

이제 $j $ 와 $ i $ 를 움직이며 $ SP $ 를 계산한다.

$ P_0 $ 인 $ a $ 가 나타나는 인덱스는 $ 4 $ 이므로 $ P_4 $ 에 $i $ 가 도착하기 전까지 $ SP $ 는 $ 0 $ 이다.

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$	$j$
$i$				$ \rightarrow $	$i$
$SP$	0	0	0	0	1

이제 $ P_0 $ 와 같은 곳을 찾았으니 $ j $ 도 같이 움직이며 비교해나간다.

$ P_1 $ 과 $ i $ 가 다음 이동한 $ P_5 $ 역시 동일하니 아래와 같이 만들어진다.

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$	$ \rightarrow $	$j $
$i$					$ \rightarrow $	$ i $
$SP$	0	0	0	0	1	2

그 다음도 동일하니 다음과 같다.

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$		$ \rightarrow $	$ j $
$i$						$ \rightarrow $	$ i $
$SP$	0	0	0	0	1	2	3

그런데 그 다음인 $ P_7 $ 과 $ P_3 $ 을 비교하니 다르다. 그렇다면 $ j $ 는 다시 돌아간다. 어디로 이동하냐면 $ j $ 가 있는 곳의 직전 인덱스의 $ SP $ 의 값인 인덱스로 돌아간다. 그리고 그 자리에서 다시 비교하고, 없으면 다시 돌아가고 하는 방식으로 $ SP$ 를 채운다.

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$			$ \leftarrow $	$ j $
$i$			$ \downarrow $				$ \rightarrow $	$ i $
$SP$	0	0	0	0	1	2	3

$ P $	$a$	$c$	$b$	$d$	$a$	$c$	$b$	$a$
index	0	1	2	3	4	5	6	7
$j$	$j$
$i$								$ i $
$SP$	0	0	0	0	1	2	3	1

단 여기서 $ j $ 가 움직이는 것은 비교를 위해 이동시킨 것이지 실제로는 $ j $ 자체가 아니라 다른 값을 통해 비교한다. 자세한 내용은 아래 코드를 참고하면 된다.

 

---

최대 접두부 테이블 활용

 

최대 접두부 테이블을 만들었다면 이를 활용해 불필요한 비교를 줄인다. 먼저 포인터 두 개 $ i $, $ j $ 를 가정하자. $ i $ 는 텍스트에서 현재 검사 중인 위치이고, $ j $ 는 패턴에서 현재 검사 중인 위치이다. 두 글자가 같으면 한 칸씩 전진한다. 여기까지는 브루트포스 알고리즘과 동일하다.

만약 불일치가 있다면 이미 맞았던 글자 수는 $ j $ 이다. 이때 다시 검사해도 소용없는 부분을 건너뛰기 위해 지금까지 맞은 접두사 안에서 그 자체가 또 접미사가 되는 길이를 활용하는데, 그 값이 $ SP_{j-1} $ 이다. 따라서 $ j $ 를 $ SP_{j-1} $ 로 점프한다. 단 텍스트 포인터 $ i $ 는 유지한다. 이렇게 하면 이미 확인한 글자는 다시 보지 않고 비교할 수 있다.

점프 후 다시 움직이며 $ i $ 와 $ j $ 를 전진한다. 만약 $ j $ 가 $ m $ 에 도달하면 하나의 매칭을 찾는 것이다.

매칭을 찾았다면 위치를 기록하고 $ j $ 를 $ SP_{m-1} $ 로 다시 줄여 비교를 계속한다.

vector<int> compute_SP(const string& pattern) {
    int m = pattern.length();
    vector<int> SP(m, -1);
    int k = -1;
    for (int j = 1; j < m; j++) {
        while (k >= 0 && pattern[k + 1] != pattern[j]) {
            k = SP[k];
        }
        if (pattern[k + 1] == pattern[j]) {
            k++;
        }
        SP[j] = k;
    }
    return SP;
}

vector<int> kmp(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> result;
    vector<int> SP = compute_SP(pattern);
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && pattern[j + 1] != text[i]) {
            j = SP[j];
        }
        if (pattern[j + 1] == text[i]) {
            j++;
        }
        if (j == m - 1) {
            result.push_back(i - m + 1);
            j = SP[j];
        }
    }
    return result;
}