🍓

[JS] KMP 알고리즘


문자열 검색

문자열 검색 문제는 문자열 HH가 주어졌을 때 문자열 NN을 부분 문자열로 포함하는지 확인하고, 포함한다면 NN과 일치하는 부분 문자열의 시작 위치를 찾는 문제다.

이 문제를 풀 수 있는 가장 간단한 방법은 HH의 가능한 모든 위치에서 다 시도해보는 방법이다. HH의 각 위치의 부분 문자열이 NN과 일치하는지 일일히 다 확인하는 것이다.

시작 위치의 수는 O(H)O(|H|)가 되고, 각각 비교에 걸리는 시간은 O(N)O(|N|)이 걸리기 때문에, 총 걸리는 시간은 O(HN)O(|H||N|)이다.

C의 strstr(), C++의 string::find(), 자바의 indexOf(), 자바스크립트의 String.prototype.indexOf() 등 대부분 표준 라이브러리에서 사용된다.

KMP 알고리즘

더 빠르게 할 수는 없을까?

위에서 본 방법은 간단하지만 최선의 방법은 아니다. 검색 과정에서 얻는 정보를 버리지 않고 활용하면 시간을 절약할 수 있다.

어떤 정보를 활용할 수 있을까? 어떤 긴 문자열 HH에서 NN="aabaabac"를 찾는다고 해보자.

어떤 시작 위치 ii에서부터 NN을 맞췄는데 첫 일곱 글자 "aabaaba"가 일치했지만 마지막 글자는 불일치했다. 이때, 단순한 알고리즘은 바로 다음 위치인 i+1i+1에서 매칭을 다시 시작할 것이다. 하지만 일곱 글자가 대응됐다는 사실을 통해 우리는 답이 될 가능성이 있는 다음 위치를 특정할 수 있다.

우리는 ii부터 불일치한 위치 전까지는 HH에 어떤 문자가 있는지 알 수 있다(...aabaaba...). 그렇기 때문에 다음 위치 i+1i+1에서 시작하면 NN과 절대 일치할 수 없다는 사실을 알 수 있다. 왜냐하면 i+1i+1에서 시작하면 첫 두 글자가 "ab"인 것을 알고 있기 때문이다. i+2i+2의 경우도 마찬가지다. "b"로 시작하는 것을 알고 있기 때문에 일치할 수 없다.

이런 식으로 i+6i+6까지 대응해보면 답이 될 가능성이 있는 시작위치는 i+3i+3 (aaba...)과 i+6i+6 (a...) 밖에 없다는 것을 알 수 있다. 따라서 시작 위치를 i+1i+1이 아닌 i+3i+3부터 검색을 시작하면 된다. ii에서 뿐만 아니라 어느 위치 xx에서도 일곱 글자가 일치했다면 x+3x+3에서 시작하면 된다. 어느 위치에서도 일곱 글자가 일치하면 위에서 알아낸 정보는 똑같이 특정할 수 있기 때문이다.

즉, 불일치가 일어났을 때 지금까지 '일치한 글자 수'를 이용해 '다음 시작 위치'를 빠르게 알아낼 수 있다는 것이다.

일치한 글자 수는 항상 0에서 N|N| 사이의 정수이기 때문에, 전처리 과정에서 이 정보들을 미리 계산해 저장해 사용할 수 있다.

이런 최적화를 사용한 방식이 바로 'KMP(Knuth-Morris-Pratt) 알고리즘'이다.

다음 시작 위치 찾기

위 예에서 i+ki+k가 후보가 될 수 있기 위해서는 어떤 특징을 만족해야 할까?

i+ki+k부터 i+6i+6의 글자는 "aabaaba"의 뒷부분에 해당하는 글자다. 시작 위치를 i+ki+k로 옮겼을 때 이 글자는 "aabaaba"의 앞부분과 일치해야 후보가 될 수 있다.

예를 들어 kk가 4라면, i+4i+4부터 i+6i+6까지 글자는 "aba"다. 이 글자는 "aabaaba"의 앞부분과 일치하지 않기 때문에 후보가 될 수 없다.

즉, mm개 일치했을 때 시작 위치 i+ki+k에서 답을 찾을 수 있기 위해서는 N[...m1]N[...m-1]의 길이 mkm-k인 접두사와 접미사가 같아야 한다. i+3i+3의 경우 길이 73=47-3=4인 접두사는 "aaba"이고 접미사도 "aaba"이기 때문에 다음 시작 위치가 될 수 있다.

KMP 알고리즘은 전처리 과정에서 다음과 같이 정의되는 배열 pi를 계산한다.

  • pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

이 배열을 통해 어디까지 일치했는지 i가 주어졌을 때 다음 시작 위치를 알 수 있다. 이 배열을 흔히 '부분 일치 테이블'이라고 부른다.

예제의 부분 일치 테이블은 다음과 같다.

iN[..i]접두사이면서 접미사인 최대 문자열pi[i]
0a-0
1aaa1
2aab-0
3aabaa1
4aabaaaa2
5aabaabaab3
6aabaabaaaba4
7aabaabac-0

구현

적절한 전처리 과정을 통해 pi를 계산했다고 치고 구현해보자. KMP 알고리즘 구현에서 고려해야 할 점은 다음과 같다.

  • m글자 일치한 후 불일치가 발생했을 때 다음 시작 위치는 m - pi[m - 1]만큼 증가시키면 된다.
  • 시작 위치를 옮긴 후에는 첫 글자부터 대응할 필요 없이 pi[m - 1]부터 확인하면 된다(접두사는 같은 것을 알기 때문).
  • 답을 찾은 경우 후에는 불일치가 발생한 경우와 같이 다음 시작 위치에서부터 검색을 계속하면 된다.
1function kmpSearch(H, N) {
2 const ret = [];
3 const pi = getPartialMatch(N);
4 let begin = 0, matched = 0;
5 while(begin <= H.length - N.length) {
6 if(matched < N.length && H[begin + matched] === N[matched]) {
7 // 모두 일치했다면 답에 추가한다.
8 if(++matched === N.length ) ret.push(begin);
9 }
10 else {
11 // 한 글자도 일치하지 않으면 다음 시작 위치에서 탐색한다.
12 if(matched === 0) begin++;
13 else {
14 begin += matched - pi[matched - 1];
15 matched = pi[matched - 1];
16 }
17 }
18 }
19 return ret;
20}

부분 일치 테이블 생성하기

부분 일치 테이블을 생성하는 가장 간단한 방법은 NN의 각 접두사에 대해 가능한 답을 하나씩 모두 시도하는 것이다. 하지만 이것은 O(N3)O(|N|^3) 시간이 걸리기 때문에 비효율적이다.

대신 각 접두사의 pi를 따로 계산하는 것이 아닌 모든 접두사에 대해 계산함으로써 최적화할 수 있다.

1function getPartialMatchNaive(N) {
2 const pi = new Array(N.length).fill(0);
3 for(let begin = 1; begin < N.length; begin++) {
4 for(let i = 0; i + begin < N.length; i++) {
5 if(N[begin + i] != N[i]) break;
6 pi[begin + i] = Math.max(pi[begin + i], i + 1);
7 }
8 }
9 return pi;
10}

NN="aabaabac"에서 자기 자신을 찾으면서, 두 글자 N[i]N[begin + i]가 같다면 pi[begin + i]를 갱신해주면 된다.

여기서 검색 과정을 KMP 알고리즘으로 더욱 최적화 할 수 있다. 바로 이전 단계에서 얻은 pi 값을 사용하는 것이다.

1function getPartialMatch(N) {
2 const pi = new Array(N.length).fill(0);
3 let begin = 1, matched = 0;
4 while(begin + matched < N.length) {
5 if(N[begin + matched] === N[matched]) {
6 matched++;
7 pi[begin + matched - 1] = matched;
8 }
9 else {
10 if(matched === 0) begin++;
11 else {
12 begin += matched - pi[matched - 1];
13 matched = pi[matched - 1];
14 }
15 }
16 }
17 return pi;
18}

이렇게 구현한 전체 KMP 알고리즘의 시간 복잡도는 O(N+H)O(|N| + |H|)다.


참조: 알고리즘 문제 해결 전략 2