Algorithm - < 문자열 매칭 네 가지 >

개요

끝이 안 보이는 줄. 빨강, 파랑, 노랑, 초록 모자를 차례로 쓴 네 명을 찾아야 한다.

맨 앞 사람부터 모자를 본다. 빨강이 아니다. 한 칸 옆. 또 아니다. 한 칸 옆..

그러다 네 번째 사람을 먼저 봤다고 해보자. 보라 모자다.

..그럼 이 사람이 끼어 있는 네 명은 볼 필요도 없잖아?

한 명 보고 네 칸을 건너뛴다. 보이어-무어가 패턴을 오른쪽 끝부터 비교하는 이유다. 찾는 줄이 길수록 더 멀리 뛴다.

이번에 배운 건 텍스트 안에서 패턴의 위치를 찾는 알고리즘 네 가지다. 브루트포스, 라빈-카프, 보이어-무어( 호스풀 방식 ), KMP. 넷은 결국 같은 두 질문에 다르게 답한다.

실패했을 때 패턴을 얼마나 밀 수 있는가.
이미 비교한 정보를 어떻게 재사용하는가.

보이어-무어가 오른쪽부터 보는 것도, KMP가 if가 아니라 while로 되돌아가는 것도 이 두 질문으로 설명된다. 마지막에는 버그 두 개가 심어진 C++ KMP 코드를 고치며 나온 구현 점검표를 정리했다.

네 알고리즘 비교

	핵심 아이디어	전처리	최악	보통
브루트포스	모든 위치에서 한 글자씩	없음	O(NM)	입력에 따라 다름
라빈-카프	M글자 비교를 해시 비교 1번으로	패턴 해시 O(M)	O(NM)	O(N+M)
보이어-무어( 호스풀 )	오른쪽부터 비교, 크게 점프	skip 표	O(NM)	N보다 적은 비교도 가능
KMP	맞은 정보 재사용, 텍스트 되감기 없음	pi O(M)	O(N+M)	O(N+M)

N은 텍스트 길이, M은 패턴 길이다. 아래에서 “정렬 위치 s”는 패턴의 첫 글자를 텍스트의 s번 칸에 맞춰 놓은 상태를 말한다.

브루트포스 — 두 가지를 버린다

모든 정렬 위치에서 패턴을 왼쪽부터 한 글자씩 비교한다. 틀리면 i = i - j로 텍스트 포인터를 이번 정렬의 시작 위치로 되감고, 한 칸 뒤에서 다시 시작한다.

여기서 버리는 게 두 가지다.

정렬 위치를 한 칸씩만 옮긴다
이미 맞은 글자 정보를 버리고 텍스트 포인터가 뒤로 간다

최악은 T = aaaaaaaaaa, P = aaab 같은 입력이다. 7개 정렬 위치마다 aaa를 맞추고 b에서 틀려서 비교가 28번이다. 다만 무작위에 가까운 텍스트라면 대부분 1~2글자 만에 틀리니 실제로는 O(NM)만큼 느리지 않다.

나머지 세 알고리즘은 이 두 낭비를 하나씩 줄인다. 라빈-카프는 한 정렬 위치의 비교 비용을, 보이어-무어는 이동 거리를, KMP는 되감기를 줄인다.

라빈-카프 — M글자 비교를 숫자 하나로

문자열을 숫자( 해시 )로 바꾸면 M글자 비교가 숫자 비교 한 번이 된다. 문제는 창을 한 칸 밀 때마다 해시를 처음부터 다시 계산하면 그게 또 O(M)이라는 것이다.

롤링 해시는 이걸 O(1)로 만든다. 빠지는 글자를 빼고, 자리를 하나 올리고, 들어오는 글자를 더한다.

new = (old − out × base^(M−1)) × base + in

10진수로 보면 바로 보인다. 6843에서 창을 밀어 8432를 만들려면

6843 − 6×10³ = 843 ( 빠지는 6 제거 )
843 × 10 = 8430 ( 자리 올림 )
8430 + 2 = 8432 ( 들어오는 2 추가 )

mod를 쓰면 충돌이 생긴다

글자를 base 256 숫자로 보면 길이 80인 패턴은 256⁸⁰이라 정수 범위를 한참 넘는다. 그래서 큰 소수 q로 나머지를 취한다. 그 대가로 서로 다른 문자열이 같은 해시를 가질 수 있다( 해시 충돌 ). 해시가 같으면 실제 글자를 비교해 확인해야 하는 이유다.

최악이 O(NM)인 것도 여기서 나온다. 충돌이 매 위치에서 나면 매번 M글자를 확인한다.

C++로 짤 때는 하나 더 조심해야 한다. old - out * pow가 음수가 될 수 있는데, C++의 %는 음수에 음수 나머지를 돌려준다( 파이썬은 양수 ). 일반형은 ((x % q) + q) % q다.

// high = base^(M-1) % q 를 미리 구해 둔다
h = (h - out * high % q + q) % q;   // 빠지는 글자 제거, +q로 음수 방지
h = (h * base + in) % q;            // 자리 올림 + 들어오는 글자

DNA라면 충돌이 아예 없다

A·C·G·T 네 글자는 2비트로 표현된다. 64비트 정수에는 32글자까지 손실 없이 들어가니, M ≤ 32면 서로 다른 문자열은 반드시 다른 숫자가 된다( 완전 해시 ). 충돌이 없으니 mod도, 글자 확인도 필요 없다. 길이 10짜리 패턴은 20비트라 넉넉하고, 길이 80이면 160비트라 다시 mod가 필요하다.

보이어-무어 — 오른쪽 끝 한 칸이 M개 위치를 판정한다

호스풀 방식은 패턴을 오른쪽 끝부터 비교하고, 틀리면 패턴 마지막 칸 아래에 있는 텍스트 글자 X로 이동 거리를 정한다.

왜 오른쪽부터인가

정렬 위치 s에서 k번째 칸이 틀렸고 그 텍스트 글자가 패턴에 아예 없다고 해보자. 그 텍스트 칸을 덮는 정렬 위치는 s부터 s+k까지 k+1개고, 어디에 놓든 그 칸에서 틀린다. 한 번의 비교로 k+1개 위치가 탈락한다.

그러면 k가 클수록 이득이다. 왼쪽부터 비교하면 대부분 k=0 근처에서 틀려서 1칸 안팎만 밀 수 있다. 오른쪽부터 비교하면 첫 비교가 k=M−1이라 최대 M칸을 민다. 가장 많은 정렬 위치를 한 번에 판정하는 칸을 먼저 보는 것이다.

왼쪽부터 비교하면 X에서 틀려 s=0만 탈락하고, 오른쪽부터 비교하면 W에서 틀려 s=0~3이 함께 탈락한다

개요의 보라 모자가 이 그림의 W다. 패턴에 없는 글자 하나가 그 칸을 끼고 있는 정렬 위치를 한꺼번에 지운다.

패턴이 길수록 빨라지는 것도 같은 이유다. M이 커지면 한 번에 밀 수 있는 최댓값이 커지고, 운이 좋으면 비교 횟수가 대략 N/M까지 줄어든다. 텍스트 글자를 전부 보지도 않고 끝나는 셈이라 브루트포스는 물론 KMP보다도 적게 비교할 수 있다.

얼마나 밀어도 되나

패턴을 d칸 밀면 X가 있는 텍스트 칸 아래에는 P[M−1−d]가 온다. 그 위치에서 매칭될 가능성이라도 있으려면 P[M−1−d] == X여야 한다. 가능한 위치를 건너뛰면 안 되니 그런 d 중 가장 작은 것을 고른다. 그게 X가 패턴에서 가장 오른쪽에 나오는 자리다.

모자 줄로 돌아가면, 네 번째 자리 사람이 보라가 아니라 파랑 모자일 때는 네 칸을 건너뛰면 안 된다. 그 사람이 묶음의 두 번째 자리가 되도록 두 칸만 밀어야 한다.

WORLD에서 X=O이면 d=1에 L, d=2에 R, d=3에 O가 와서 3칸 이동

skip[X] = M − 1 − (P[0..M−2]에서 X가 마지막으로 나오는 인덱스)
          패턴에 없으면 M

마지막 칸을 빼고 찾는 이유는 d=0 때문이다. 포함하면 패턴 마지막 글자와 X가 같을 때 skip이 0이 나와서 제자리에서 무한 루프를 돈다.

몇 개 계산해 보면 이렇다.

패턴	skip 표
`rithm`	r 4, i 3, t 2, h 1, m 5, 그 외 5
`PAPER`	P 2, A 3, E 1, R 5, 그 외 5
`WORLD`	W 4, O 3, R 2, L 1, D 5, 그 외 5

PAPER의 P는 0번과 2번에 있는데, 더 오른쪽인 2번 기준으로 4−2 = 2다. M칸을 밀어도 안전한 건 X가 패턴에 아예 없을 때뿐이다. X가 패턴에 있는데 M칸을 밀면 X가 맞춰지는 가까운 정렬 위치를 확인도 안 하고 지나쳐서 매칭을 놓칠 수 있다.

vector<int> horspool(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    vector<int> skip(256, m);                       // 패턴에 없는 글자는 M칸
    for (int k = 0; k < m - 1; k++)                 // 마지막 칸은 빼고
        skip[(unsigned char)P[k]] = m - 1 - k;      // 오른쪽 등장일수록 나중에 덮어써서 작은 값이 남는다
    vector<int> res;
    int s = 0;                                      // 정렬 위치
    while (s + m <= n) {
        int k = m - 1;                              // 오른쪽 끝부터
        while (k >= 0 && T[s + k] == P[k]) k--;     // 맞는 동안 왼쪽으로
        if (k < 0) res.push_back(s);                // 전부 맞음
        s += skip[(unsigned char)T[s + m - 1]];     // 마지막 칸 아래 글자 X로 이동 거리 결정
    }
    return res;
}

약점: 작은 알파벳과 반복 텍스트

DNA처럼 글자가 4종류뿐이면 대부분의 글자가 패턴 안에 있어서 skip이 짧아진다. 크게 뛰는 장점이 줄어든다.

최악은 T = aaaaaaaaa, P = baaaa다. 정렬 위치마다 a 4개를 맞추고 b에서 틀린 뒤, X = a의 skip이 1이라 한 칸만 민다. 5개 위치에서 5번씩 25번 비교하니 O(NM)이다. 호스풀은 원래 보이어-무어를 단순하게 줄인 판이다. 원형의 good suffix 규칙에 Galil 규칙까지 더하면 최악도 선형이 된다.

KMP — 맞은 글자는 텍스트를 다시 볼 필요가 없다

KMP의 출발점은 이 관찰이다. 패턴과 j글자가 맞은 뒤 틀렸다면, 그 j칸의 텍스트 내용은 패턴 앞 j글자와 같다. 이미 알고 있는 내용이니 다음 정렬 위치는 텍스트를 다시 보지 않고 패턴만으로 정할 수 있다.

d칸 밀어도 되는지 = 보더

맞은 부분 아래로 패턴을 d칸 밀면, 맞은 부분의 길이 (j−d) 접미사와 패턴의 길이 (j−d) 접두사가 겹친다. 이 둘이 같아야 그 위치가 후보로 남는다. 접두사이면서 동시에 접미사인 부분을 보더( border )라고 부른다.

ababa를 1~4칸 밀어 보면 2칸( 보더 aba )과 4칸( 보더 a )만 가능

가장 작은 이동은 가장 긴 보더에서 나온다. 그보다 작게 미는 위치는 겹치는 부분이 달라서 실패가 확정이니 건너뛰어도 안전하다.

그래서 패턴의 각 접두사마다 가장 긴 보더 길이를 미리 구해 둔다.

pi[k] = P[0..k]의 가장 긴 진( proper ) 보더 길이
진 보더는 문자열 전체를 빼고 센다. 전체를 포함하면 항상 자기 자신이 가장 긴 보더라 d=0, 즉 안 미는 게 된다

k	0	1	2	3	4	5	6
P[k]	a	b	a	b	a	c	a
pi[k]	0	0	1	2	3	0	1

틀리면 j = pi[j-1]로 줄이고 텍스트 포인터 i는 그대로 둔다. 보더 부분은 이미 맞다고 보장되니 다시 비교하지 않는다. 패턴을 “민다”는 말이 코드에서는 j를 줄이는 것이다.

검색을 따라가 보면 i가 한 번도 뒤로 가지 않는다. T = abababaca, P = ababaca에서

i=0~4: ababa까지 맞아서 j=5
i=5: P[5]=c와 T[5]=b가 틀림 → j = pi[4] = 3. i는 5에 그대로 두고 P[3]=b와 비교
맞고, 끝까지 맞아서 시작 위치 2를 찾는다

되돌리기는 한 번으로 끝나지 않는다

나는 j = pi[j-1]을 한 번 적용하면 끝나는 줄 알았다.

그런데 j = pi[j-1]이 주는 건 후보 하나다. 옮긴 위치에서 다음 글자까지 맞아야 끝난다. 틀리면 다음 후보로 가야 하는데, 두 번째로 긴 보더는 가장 긴 보더의 가장 긴 보더다. 그래서 pi를 다시 따라간다. ababa라면 aba → a → 없음 순서다.

P = aabaab( pi = 0 1 0 1 2 3 )에서 aabaa까지 맞고 다음 텍스트 글자가 a인 경우를 보면 한 번으로는 안 끝난다.

aabaa에서 a를 만나 j=5 → 2 → 1을 거쳐 최종 j=2

보장된 부분이 aabaa → aa → a로 줄어들다가, 마지막에 a가 맞아서 aa가 된다. 이렇게 맞거나 j가 0이 될 때까지 반복하니 if가 아니라 while이어야 한다.

pi[j-1]과 pi[j]는 j의 뜻으로 고른다

같은 코드 안에서 pi[j-1]과 pi[j]가 둘 다 나온다. 식 모양으로 외우면 헷갈리고, pi에는 마지막으로 맞은 글자의 인덱스를 넣는다는 규칙 하나로 고르면 된다.

위치	이때 j의 뜻	올바른 식
while 안( 불일치 )	맞은 글자 수	`pi[j-1]`
성공 분기( j 증가 전, j == m−1 )	방금 맞은 글자의 인덱스	`pi[j]`

while 안에서 pi[j]를 쓰면 방금 틀린 글자까지 포함한 접두사의 보더로 되돌아간다. 위 예제라면 맞은 건 ababa인데 ababac의 보더를 쓰는 꼴이다.

pi 생성도 KMP다

pi를 만드는 과정은 패턴을 자기 자신 안에서 KMP로 검색하는 것과 같다. 되돌릴 때 쓰는 pi[j-1]은 항상 j < i라서 이미 계산된 칸이다. 앞에서 구한 값으로 뒤를 채우는 DP 구조다.

왜 O(N+M)인가

while이 안에 있는데 선형인 이유는 j의 증감으로 셀 수 있다.

j는 텍스트 한 글자당 최대 1 늘어난다
while을 한 번 돌 때마다 j는 반드시 줄어든다
j는 0 밑으로 내려가지 않는다

그러니 전체 감소량 ≤ 전체 증가량 ≤ N이다. while이 통틀어 N번을 넘게 돌 수 없어서 검색은 O(N), 같은 논리로 pi 생성은 O(M)이다.

버그 두 개가 심어진 KMP

문제는 버그 두 개가 심어진 C++ KMP 코드에서 버그를 찾는 것이었다. 아래는 버그가 있는 줄만 재구성한 것이다.

// buildPi 안쪽 — 버그 1
if (j > 0 && P[i] != P[j])      // 되돌리기가 한 번만 일어난다
    j = pi[j - 1];

// kmpSearch 안쪽 — 버그 2
while (j > 0 && T[i] != P[j])
    j = pi[j];                  // 맞은 글자 수가 아니라 인덱스로 읽었다

버그 1: if — pi가 0 0 1 2 3 1 1로 나온다

첫 번째는 앞에서 내가 착각했던 바로 그 생각이 코드가 된 것이다. ababaca의 pi를 이 코드로 만들면 0 0 1 2 3 1 1이 나온다( 정답 0 0 1 2 3 0 1 ).

i=5에서 c를 만나 j가 3 → 1로 한 번 되돌아가고, P[1]=b도 c와 틀리는데 거기서 멈춰서 j=1이 그대로 pi[5]에 들어간다. ababac의 보더가 a라는 뜻인데 ababac는 c로 끝나니 말이 안 된다. 틀린 pi[5]는 다음 칸 계산에도 쓰인다.

이 pi로 abababaca를 검색하면 위치 2를 제대로 찾는다. i=5의 되돌리기가 pi[4]만 쓰고 틀린 pi[5]는 안 건드리기 때문이다. 틀린 칸을 지나가는 입력을 넣어야 드러나는데, ababacbabaca를 넣으면 매칭이 없는데도 위치 5를 보고한다. ababac 뒤에서 b와 틀린 순간 틀린 pi[5]=1이 “a 한 글자는 맞아 있다”고 우기는 탓이다. 실제로 그 자리에 있는 건 c다.

버그 2: pi[j] — 출력이 비어 있다

두 번째는 while 안의 j = pi[j]다. pi가 정답이어도 T = abababaca, P = ababaca에서 아무것도 출력하지 않는다.

i=5에서 틀린 순간 j는 “맞은 글자 수 5”인데, pi[5]는 ababac의 보더 길이 0이다. pi[4]=3으로 aba가 맞아 있다는 보장을 써야 할 자리에서 그걸 다 버리고 처음부터 다시 맞추니 위치 2를 놓친다.

버그가 있어도 통과하는 테스트

같은 버그 코드로 T = aaaaa, P = aa를 돌리면 0 1 2 3이 정상 출력된다. 불일치가 한 번도 나지 않아 while에 들어가지 않기 때문이다. 버그 1의 pi도 aa에서는 0 1로 정답과 같다.

테스트 통과가 정답을 보장하지 않는다. 버그가 있는 경로를 실제로 지나가는 입력이 필요하다. KMP라면 되돌리기가 연쇄로 일어나는 패턴( ababaca, aabaab )과, 되돌린 뒤 다시 틀리는 텍스트가 그런 입력이다.

고친 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// pi[k] = P[0..k]의 가장 긴 진 보더 길이
vector<int> buildPi(const string& P) {
    int m = P.size();
    vector<int> pi(m, 0);
    int j = 0;                              // 지금까지 맞은 글자 수
    for (int i = 1; i < m; i++) {           // i=0부터면 자기 자신 전체와 비교하게 된다
        while (j > 0 && P[i] != P[j])       // 맞거나 j=0이 될 때까지 보더를 따라 되돌린다
            j = pi[j - 1];
        if (P[i] == P[j]) j++;              // 맞으면 한 글자 늘린다
        pi[i] = j;
    }
    return pi;
}

vector<int> kmpSearch(const string& T, const string& P) {
    vector<int> pi = buildPi(P);
    int n = T.size(), m = P.size();
    int j = 0;                              // 지금까지 맞은 글자 수
    vector<int> res;
    for (int i = 0; i < n; i++) {           // i는 한 번도 되돌아가지 않는다
        while (j > 0 && T[i] != P[j])       // 불일치: 보더로 되돌리기
            j = pi[j - 1];                  // j = 맞은 글자 수
        if (T[i] == P[j]) {
            if (j == m - 1) {               // 마지막 글자까지 맞음
                res.push_back(i - m + 1);   // 시작 위치 기록
                j = pi[j];                  // j = 방금 맞은 글자의 인덱스, 다음 매칭을 이어서 찾는다
            } else {
                j++;
            }
        }
    }
    return res;
}

int main() {
    for (int x : kmpSearch("abababaca", "ababaca")) cout << x << ' ';   // 2
    cout << '\n';
}

매칭에 성공한 뒤 j를 갱신하지 않고 그냥 j++하면 j가 m이 되어 다음 비교에서 패턴 밖인 P[m]을 읽는다.

KMP 구현 점검표

pi 생성은 i=1부터, 검색은 i=0부터
불일치 while( j > 0 조건 포함 )이 “맞으면 j 증가”보다 먼저
while 안은 pi[j-1]
매칭 성공 후 j 갱신
1-based 출력을 요구하는 문제면 +1

확인용 입력은 이것들이다. 버그가 지나가는 경로를 일부러 고른 것들이다.

입력	기대 결과
`ababaca`의 pi	`0 0 1 2 3 0 1`
`aabaab`의 pi	`0 1 0 1 2 3`
`abababaca`에서 `ababaca`	2
`ababacbabaca`에서 `ababaca`	없음
`aaaaa`에서 `aa`	0 1 2 3
`rithm`의 skip( 글자 순서대로 )	4 3 2 1 5

게임과 실무에서 쓰는 자리

KMP는 스트림을 그대로 처리한다. 텍스트 포인터가 되돌아가지 않으니 텍스트 전체를 저장할 필요가 없다. 글자가 하나 들어올 때마다 상태 j만 갱신하는 유한 상태 기계다. 격투 게임에서 ↓ ↘ → + P 같은 커맨드를 입력 스트림에서 감지하는 문제가 이 구조와 같다. 실제 게임은 “몇 프레임 안에 입력해야 한다” 같은 시간 창 조건이 더 붙는다.

pi로 반복 주기를 구한다. 문자열의 최소 주기는 n − pi[n−1]이다. abcabcabc라면 9 − 6 = 3이라 abc가 반복된다. n이 주기로 나누어떨어질 때만 완전한 반복이다( abcab도 주기는 3이지만 abc가 딱 맞게 반복되진 않는다 ). 리플레이나 행동 로그에서 같은 루프가 도는지 감지할 때 쓸 수 있다.

아호-코라식은 KMP를 트라이에 얹은 것이다. KMP의 실패 함수를 트라이 위에 만들면 여러 패턴을 텍스트 한 번 스캔으로 찾는다. 금칙어 채팅 필터를 만들 때 흔히 쓰는 방식이다.

롤링 해시는 바뀐 부분만 보내는 데 쓴다. rsync가 롤링 체크섬으로 바뀐 블록만 골라 전송하는 게 이 아이디어고, 게임 델타 패치도 같은 계열이다. 2D로 늘리면( 행마다 롤링 해시 → 그 결과에 열 방향 롤링 해시 ) 타일맵에서 특정 모양을 찾을 수 있다.

직접 짜기 전에 표준 라이브러리부터.

C++17 <functional>에 std::boyer_moore_searcher와 std::boyer_moore_horspool_searcher가 있어서 std::search에 넘기면 된다
.NET의 string.IndexOf(string)은 기본이 현재 문화권 규칙 비교다. 데이터 키나 ID를 찾을 때는 StringComparison.Ordinal을 명시하는 게 안전하다

소감

진짜로 알고리즘 공부라는 본질에 맞는 여러 다양한 시각들을 보는게 재밌었다!