Algorithms/String Algorithms

2.19.2 KMP

개념

시작 위치마다 비교하는 방법

패턴 탐색은 문자열에서 특정 문자열이 등장하는 위치를 찾는 문제입니다. 찾으려는 문자열을 패턴이라고 합니다. 가장 직접적인 방법은 시작 위치를 한 칸씩 옮기면서 패턴의 첫 문자부터 차례로 비교하는 것입니다.

대상 문자열 길이가 NN, 패턴 길이가 MM이면 시작 위치는 00부터 N−MN-M까지 확인합니다. 그보다 뒤에서 시작하면 패턴의 끝이 대상 문자열을 벗어납니다. 예를 들어 ABABABA에서 ABA는 위치 0,2,40,2,4에 등장합니다. 시작 위치를 한 칸씩 옮기므로 서로 겹치는 등장 위치도 찾습니다.

대상 문자열이 AAAAAA, 패턴이 AAAB이면 각 시작 위치에서 AAA를 비교한 뒤 마지막 문자에서 실패합니다. 다음 위치에서도 같은 AAA를 처음부터 비교합니다. 이렇게 시작 위치마다 최대 MM개 문자를 비교하므로 최악의 시간복잡도는 O(NM)O(NM)입니다. KMP는 앞서 일치한 부분의 정보를 활용하여 이 반복 비교를 줄입니다.

이미 일치한 부분 활용하기

KMP는 문자열과 패턴을 비교하다가 불일치했을 때, 이미 일치한 부분의 정보를 이용하여 다음 비교 위치를 정하는 알고리즘입니다. 대상 문자열의 위치를 뒤로 되돌리지 않고 탐색합니다.

접두사 함수

접두사는 문자열의 앞에서 시작하는 부분 문자열이고 접미사는 끝에서 끝나는 부분 문자열입니다. 패턴의 위치 ii까지인 부분 문자열에서, 자기 자신을 제외하고 접두사와 접미사가 같은 가장 긴 길이를 π(i)\pi(i)로 정합니다.

패턴 ABABA의 접두사 함수 값은 다음과 같습니다.

위치01234
문자ABABA
접두사 함수00123

마지막 위치에서는 ABA가 접두사이자 접미사이므로 값이 33입니다.

접두사 함수를 왼쪽부터 구할 때 직전 위치의 일치 길이를 이어서 확인합니다. 다음 문자가 다르면 그 일치 부분의 접두사 함수 값으로 길이를 줄여 다시 비교합니다.

패턴 탐색

현재까지 일치한 패턴의 길이를 jj라고 합니다. 다음 문자가 다르면 jj를 π(j−1)\pi(j-1)로 줄여 비교를 이어 갑니다. 일치하는 접미사가 다음 후보의 접두사가 되므로 그 부분의 재비교를 건너뛸 수 있습니다.

길이 MM의 패턴을 모두 찾으면 위치를 기록하고 jj를 π(M−1)\pi(M-1)로 바꿉니다. 이 상태에서 다음 문자를 비교하면 겹치는 등장 위치도 찾습니다.

불일치 후 이어서 비교하는 과정

대상 문자열 ABABABAC에서 패턴 ABABAC를 찾는다고 하겠습니다. 처음 다섯 글자 ABABA는 같지만, 그다음 글자는 대상 문자열에서는 B, 패턴에서는 C로 서로 다릅니다.

이미 일치한 ABABA의 끝 세 글자 ABA는 패턴의 시작 세 글자 ABA와 같습니다. 따라서 패턴 시작을 대상 문자열의 두 번째 A 위치로 옮겨도 이 세 글자는 다시 비교할 필요가 없습니다. 일치 길이를 55에서 π(4)=3\pi(4)=3으로 줄이고, 아직 처리하지 않은 대상 문자열의 B를 패턴의 네 번째 문자 B와 비교합니다. 이후 A, C도 일치하여 시작 위치 22에서 패턴을 찾습니다.

옮길 후보의 앞부분은 이미 읽은 문자열의 뒷부분과 겹칩니다. 따라서 그 뒷부분이 패턴의 접두사와 같아야 다음 후보가 될 수 있습니다. 접두사 함수는 이 조건을 만족하는 가장 긴 길이를 저장하므로, 가능한 다음 후보를 건너뛰지 않으면서 재비교를 줄입니다. 그 길이에서도 맞지 않으면 더 짧은 공통 접두사·접미사 길이를 차례로 확인합니다.

대상 문자열에서 비교할 위치는 앞으로만 이동합니다. 일치 길이를 줄이는 횟수도 앞서 일치 길이를 늘린 횟수보다 많을 수 없습니다. 따라서 같은 문자가 여러 번 반복되어도 탐색 시간은 대상 문자열의 길이에 비례합니다.

복잡도

대상 문자열 길이를 NN, 패턴 길이를 MM, 찾은 위치 수를 KK라고 합니다.

연산시간복잡도공간복잡도
접두사 함수 계산O(M)O(M)접두사 함수 O(M)O(M)
대상 문자열 탐색O(N)O(N)결과 저장 O(K)O(K)

예제

문제

문자열에서 주어진 패턴이 등장하는 모든 시작 위치를 구하여라. 서로 겹치는 등장 위치도 포함한다.

입력

첫째 줄에 문자열 SS가 주어진다. SS는 영어 대문자로 이루어져 있으며 길이는 11 이상 100100 이하이다.

둘째 줄에 패턴 PP가 주어진다. PP는 영어 대문자로 이루어져 있으며 길이는 11 이상 100100 이하이다.

출력

첫째 줄에 등장 횟수를 출력한다. 둘째 줄에 시작 위치를 작은 순서대로 공백을 사이에 두고 출력한다. 위치는 00부터 센다. 등장하지 않으면 둘째 줄을 비워 둔다.

예제 입력

ABABABA
ABA

예제 출력

3
0 2 4

예제 코드

C++20

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> pi, ans;

int main() {
    string s, p;
    int n, m, i, j;

    cin >> s >> p;
    n = (int)s.size();
    m = (int)p.size();
    pi.assign(m, 0);

    // 패턴의 접두사 함수 계산
    j = 0;
    for (i = 1; i < m; ++i) {
        // 불일치 시 이미 일치한 부분의 접두사·접미사를 이용해 다음 후보 길이로 이동
        while (j > 0 && p[i] != p[j]) {
            j = pi[j - 1];
        }
        if (p[i] == p[j]) ++j;
        // pi[i]: 패턴의 0~i 구간에서 자신을 제외한 최장 공통 접두사·접미사 길이
        pi[i] = j;
    }

    // 본문 탐색과 겹치는 일치 처리
    j = 0;
    for (i = 0; i < n; ++i) {
        // 불일치 시 이미 일치한 부분의 접두사·접미사를 이용해 다음 후보 길이로 이동
        while (j > 0 && s[i] != p[j]) {
            j = pi[j - 1];
        }
        if (s[i] == p[j]) ++j;
        // 패턴 전체 일치: 시작 위치 기록 후 겹치는 다음 일치를 위해 j 복구
        if (j == m) {
            ans.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }

    cout << ans.size() << '\n';
    for (int x : ans) {
        cout << x << ' ';
    }
    cout << '\n';
}