문자열 처리 알고리즘 - KMP

문자열 처리 알고리즘

나름 블로그의 모양새를 갖추기 위해 오늘부터 문자열처리 알고리즘에 대해 작성해보려고 한다. ㅋㅋ

---

1. KMP Algorithm

어떤 문자열(H)에서 내가 찾고자 하는 문자열(N)이 있는지 확인하려면 어떻게 해야할까?

H와 N을 하나하나씩 비교하다가 match되지 않는 부분이 나오면 N 문자열을 통째로 한칸 이동해서 다시 처음부터 비교하면 될 것이다.

그럼 시간복잡도는 $O(HN)$… ㄷㄷㄷ H와 N이 10만씩 주어지면 100억이나 된다.

Tip: H는 Hay의 약자, N은 Needle의 약자이다. 건초더미에서 바늘찾는다고 생각하면 된다. ㅋ

---

그럼 어떻게 할까?

이 문제를 $O(H+N)$만에 해결하는 방법이 있으니 그게 바로 KMP 알고리즘이다.

근데 이게 처음 코드만 보면 사실 뭐하는건지도 모르겠고, 설명들어도 점점 지쳐만 간다.

핵심만 설명하자면, 다음과 같다.

H의 길이가 10만이고 N의 길이가 100이라고 하자. H[0]부터 N을 찾아나간다. H[0],N[0]비교하고, 같다면 H[1],N[1]을 비교한다. 그러던 도중 N[49]까지는 H와 모두 일치했는데 N[50]과 H[50]이 match되지 않는다고 하자.

그럼 우리가 나름 편법(?)을 써서 하고 싶은건 H[1]과 N의 처음부터 비교하고 싶은게 아니라, 그냥 비교한 만큼을 통째로 건너뛰고 싶은 거다. 즉, N의 index는 0부터 비교하되, H의 index는 50부터 비교해버리고 싶은 것이다.

하지만 우리는 그런 짓을 하면 안된다는 것을 안다.

---

Why?

대충 안된다는 느낌은 오는데, 어디서 안된다고 정확히 잘 모르겠다라고 생각이 들지 않나? 이 부분이 KMP의 핵심 아이디어이다. H 스트링을 0->1->2->3->…->49->50에 와서 N[50]과는 다르다는 것을 확인한 뒤 H의 인덱스를 1부터 돌아가는 것이 아니라 50부터 그대로 시작하고 N은 0부터 다시 비교해서는 안되는 경우가 어떤 것일까?

그건 N의 앞부분과 H[0..49]의 뒷부분 H[x..49]에서 겹치는 부분이 생길 수 있기 때문이다. 쉽게 설명하기 위해 하나만 겹쳐보겠다. H[47..49]와 N[0..2]가 동일하다고 가정하자. 그럼 H[50]과 N[50]이 다르다고 해서 바로 H[50]과 N[0]를 비교해서는 안된다. H[47]과 N[0]을 비교해야 하는 것이다. 왜냐하면 거기서 부터 시작했을 때 H[47..146]이 N[0..99]와 같을 수 있기 때문이다.

그럼 여기서 H[47..49]가 N[0..2]와 동일하다는 것을 미리 알았다면?!
H[50]과 N[3]부터 바로 비교함으로써 H 스트링을 반복해서 볼 일이 없는 것이다. (H[50] 두 번 봤다고 태클걸지 말자. 복잡도와 아무 상관이 없다.)

일단, 미리 H[47..49]와 N[0..2]가 동일하다는 것을 미리 알았다고 가정한다면 다음과 같은 코드를 짤 수 있다.

vector<int> kmp(const string &H, const string &N) {
    vector<int> ret;
    vector<int> pi = getPartialTable(N);
    for(auto &p: pi) printf("%d ", p);
    puts("");
    int n=H.size(), m=N.size();
    int begin=0, matched=0;
    while(begin+m <= n) {
        if(H[begin+matched] == N[matched]) {
            if(++matched == m) ret.push_back(begin);
        } else {
            if(matched == 0) begin++;
            else {
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return ret;
}

위의 코드에서 getPartialTable(N)부분이 미리 알았다고 가정하는 부분들을 pi라는 vector에 대입하는 부분이다.

일단 여기서 코드 이해가 잘 안된다면 바로 다음으로 넘어가서 getPartialMatchTable이 뭐하는 놈인지 부터 살펴보는 것이 좋을 것이다. 바로 다음으로 넘어가자~

---

Failure Function (Partial Match Table)

위에서 언급했다시피 H[x..x+a]와 N[0..a]가 일치하는 부분이 몇 개 인지 미리 알기만 하면 된다. 그걸 실패함수(failure function or partial match table)라 한다.
시간복잡도부터 언급하면 Naive하게 구하는 방법은 $O(N^3)$ 이다.

윀, $O(HN)$ 피하려다가 배보다 배꼽이 더 큰 상황에 직면한 것이 아닌가?

아니다 걱정마시라… 이걸 $O(N)$에 구하는 방법이 있다. 방법은 위에서 언급한것과 비슷하다.

vector<int> getPartialTable(const string &N) {
    int m = N.size();
    int begin=1, matched=0;
    vector<int> pi(m, 0);
    while(begin+matched <= m) {
        if(N[matched] == N[begin+matched]) {
            matched++;
            pi[begin+matched-1] = matched;
        } else {
            if(matched == 0) begin++;
            else {
                begin += matched-pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return pi;
}

이게 대체 무슨 코드?

N에 대해서 앞 뒤가 똑같은 개수를 세어주는 것이다.

다시 잘 생각해보자. N[0..2]랑 H[47..49]랑 같은지 미리 알았다는 것은, 결국 N[47..49]랑 N[0..2]랑 같은지 미리 알았다는 뜻이 된다. 그래서 N에 대해서 이러한 정보들을 미리 조사한다면, 우리는 H에 해당하는 스트링을 여러번 중복해서 들여다 보지 않아도 H 스트링에서 N이라는 스트링을 빠르게 찾을 수 있는 것이다.

이러한 정보를 담는 테이블을 partial match table이라 한다. (이름은 중요하지 않다.)

말로만 설명하면 잘 이해가 안가니 N 스트링에 대한 예시를 들어보겠다.

N String: aabaabac

partial match table:

N	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
	0	1	0	1	2	3	4	0

위의 테이블에서 N[6]에 해당되는 값이 4인 이유는 “aaba abac”와 “aab aaba c”에서 굵은 글씨로 쓴 부분이 같은데, 그 길이가 4이기 때문이다.

그럼 이제 전체적인 예시를 들어보자.

H String: aabaabac
N String: aaba

맨 처음 H[0..3]과 N[0..3]이 같은 것을 찾고 난 뒤에, H[4], N[0]을 비교하고 싶지만, N에 대한 partial table이

N	[0]	[1]	[2]	[3]
	0	1	0	1

이므로 H index는 4에서 비교를 시작하면 되고, N index는 1에서 비교를 시작하면 된다.

전체 코드는 다음과 같다.

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
vector<int> getPartialTable(const string &N) {
    int m = N.size();
    int begin=1, matched=0;
    vector<int> pi(m, 0);
    while(begin+matched <= m) {
        if(N[matched] == N[begin+matched]) {
            matched++;
            pi[begin+matched-1] = matched;
        } else {
            if(matched == 0) begin++;
            else {
                begin += matched-pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return pi;
}
vector<int> kmp(const string &H, const string &N) {
    vector<int> ret;
    vector<int> pi = getPartialTable(N);
    for(auto &p: pi) printf("%d ", p);
    puts("");
    int n=H.size(), m=N.size();
    int begin=0, matched=0;
    while(begin+m <= n) {
        if(H[begin+matched] == N[matched]) {
            if(++matched == m) ret.push_back(begin);
        } else {
            if(matched == 0) begin++;
            else {
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    string H, N;
    cin >> H >> N;
    vector<int> ans = kmp(H, N);
    for(auto &p: ans) {
        for(int i=0; i<p; i++) putchar(' ');
        cout << N << "\n";
    }
    return 0;
}

위의 코드에서는 begin이라는 변수가 H 스트링에서 새로 비교를 시작할 부분의 인덱스를 의미하고 matched라는 변수가 현재 매치된 문자의 개수를 의미한다. 하지만 잘 생각해보면 begin이란 변수를 굳이 쓰지 않아도 된다는 것을 알 수 있다.

그래서 kmp알고리즘은 다음과 같이 더 짧게 코딩할 수 있다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
vector<int> kmp(const string &H, const string &N) {
    vector<int> pi(N.size(),0), ret;
    for(int i=1, matched=0; i<N.size(); i++) {
        while(matched!=0 && N[i]!=N[matched]) matched=pi[matched-1];
        if(N[i]==N[matched]) {
            matched++;
            pi[i]=matched;
        }
    }
    for(int i=0, matched=0; i<H.size(); i++) {
        while(matched!=0 && H[i]!=N[matched]) matched=pi[matched-1];
        if(H[i]==N[matched]) {
            matched++;
            if(matched==N.size()) ret.push_back(i-matched+1);
        }
    }
    return ret;
}
int main() {
    string H, N;
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> H >> N;
    vector<int> ans = kmp(H, N);
    for(auto &p : ans) {
        for(int i=0; i<p; i++) {
            putchar(' ');
        }
        printf("%s\n", N.c_str());
    }
    return 0;
}

#partial match table #failure function #kmp algorithm #string #Knuth-Morris-Pratt Pattern Matching