KMP

문자열 처리 알고리즘 – KMP#

문자열 검색 문제는 알고리즘 분야에서 자주 등장하는 주제다. 본 글에서는 대표적인 문자열 검색 알고리즘인 KMP(Knuth–Morris–Pratt) 알고리즘을 다룬다.

1. 문자열 검색 문제#

어떤 긴 문자열 H(Haystack) 안에서 특정 패턴 문자열 N(Needle)을 찾는 문제를 생각해보자. 가장 단순한 방식은 두 문자열을 한 글자씩 비교하다가 불일치가 발생하면 패턴을 한 칸 이동해 다시 처음부터 비교하는 것이다.

하지만 이 방식은 최악의 경우 $O(H × N)$ 시간 복잡도를 가진다.

이 비효율을 해결하기 위한 알고리즘이 KMP이며, KMP는 문자열 검색을 $O(H + N)$ 시간에 끝낸다.

2. 왜 “이미 비교한 문자”를 다시 보면 비효율적일까?#

예를 들어 H와 N이 일정 부분까지 잘 맞다가 마지막 글자에서 불일치가 발생했다고 하자.

H: ... a a b a a b a x ...
N:     a a b a a b a c

여기까지 7글자가 일치했는데 불일치가 발생했다면, 단순한 알고리즘은 이렇게 한다.

• 패턴 N을 한 칸 이동
• 다시 N[0]부터 완전히 새로운 비교 시작

하지만 이미 읽은 H의 문자들을 다시 읽어야 하고, 이런 일이 반복되면 H 전체를 지나치게 많이 방문하게 된다.

우리가 원하는 것은 다음과 같다.

“이미 맞았던 부분은 다시 검사하지 않고, 패턴을 적절히 건너뛰고 싶다.”

그러나 여기에는 큰 문제가 있다.

3. 패턴을 “마음대로” 건너뛰면 왜 위험한가?#

불일치가 발생했을 때, 우리는 이렇게 생각할 수 있다.

“앞에서 7글자나 맞았으니 H 인덱스를 그대로 두고 지금 위치에서 N을 다시 비교하면 되는 것 아닐까?”

하지만 이렇게 과감하게 건너뛰는 방식은 정답 매칭을 놓칠 수 있다.

예시 패턴#

N = aabaabac

이 패턴은 패턴 내부에 “겹치는”(aaba) 부분이 존재한다. (aabaabac, aabaabac)

4. Partial Match Table (Failure Function)#

이처럼 “겹치는 구간”이 존재할 때, 우리는 불일치가 발생해도 패턴을 완전히 처음부터 비교할 필요가 없다. 이를 위해 partial match table(pi 배열)을 만든다.

pi[x]: N[0..x] 구간에서, 접두사(prefix)이면서 접미사(suffix)인 문자열의 최대 길이

예시:

N = aabaabac

partial match table:

여기서 pi[6] = 4는 **“aabaaba”**에서 prefix이자 suffix인 aaba의 길이를 말한다. 이는 **“aabaaba”**에서 가질 수 있는 최대길이의 공통 prefix & suffix 문자열이다.

• prefix: aabaaba
• suffix: aabaaba

이 길이를 미리 구해 놓으면, 불일치 발생 시 패턴의 어느 위치로 점프해야 하는지를 바로 알 수 있다.

5. pi 배열을 이용한 “안전한 건너뛰기”#

앞서 본 불일치 상황을 다시 보자.

H[k..k+6] == N[0..6]
H[k+7] != N[7]

불일치 직전 matched = 7 또한 pi[6] = 4

따라서 KMP는 다음과 같은 방식으로 이동한다.

H의 다음 비교 위치 = k + (matched - pi[matched-1]) = k + (7 - 4) = k + 3
N의 다음 비교 위치 = pi[matched-1] = 4

즉,

• H는 3칸만 이동
• N은 0부터 다시 비교하는 것이 아니라, 이미 4글자가 맞았다고 보고 이어서 비교

이를 통해 H를 되돌아보지 않고도 모든 매칭 경우를 안전하게 탐색할 수 있다.

6. KMP 코드#

partial match table 생성#

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

KMP 본체#

vector<int> kmp(const string &H, const string &N) {
    vector<int> pi = GetPartialTable(N);
    vector<int> ret;
    int n = H.size(), m = N.size();
    for (int i = 0, matched = 0; i < n; i++) {
        while (matched > 0 && H[i] != N[matched])
            matched = pi[matched - 1];
        if (H[i] == N[matched]) {
            matched++;
            if (matched == m) {
                ret.push_back(i - m + 1);
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}

7. 요약#

KMP 알고리즘에 대해 요약하면 다음과 같다.

패턴 내부의 접두사/접미사 정보를 미리 계산해 두면, 불일치 시 어디로 건너뛰어야 하는지 정확히 알 수 있다.