# 문자열 매칭: KMP, Z, Rolling Hash

문자열 알고리즘의 첫 목표는 긴 텍스트 안에서 패턴이 어디에 등장하는지 빠르게 찾는 것입니다. 단순히 모든 시작 위치에서 패턴을 비교하면 최악의 경우 `O(NM)`이 됩니다. 텍스트 길이 `N`, 패턴 길이 `M`이 수십만 이상이면 다른 구조가 필요합니다.

이 레슨은 대표적인 세 도구를 한 번에 비교합니다.

| 도구 | 핵심 감각 | 주로 쓰는 상황 |
| --- | --- | --- |
| KMP | 패턴 내부의 접두사/접미사 정보를 이용해 되돌아가지 않는다 | 한 패턴을 텍스트에서 정확히 찾기 |
| Z algorithm | 각 위치에서 시작하는 접두사 일치 길이를 한 번에 계산한다 | 접두사 기준 매칭, 문자열 분석 |
| Rolling Hash | 부분 문자열을 숫자 해시로 비교한다 | 여러 구간 비교, 빠른 후보 판별 |

## 단순 비교가 느려지는 이유

텍스트 `text`의 모든 시작 위치에서 패턴 `pattern`을 비교하면 아래처럼 됩니다.

```text
for start in 0..N-M:
    for i in 0..M-1:
        compare text[start+i] and pattern[i]
```

`text = aaaaa....a`, `pattern = aaa...ab`처럼 앞부분이 계속 일치하다가 마지막에서 틀리는 입력은 같은 문자를 여러 번 비교합니다. 이 경우 최악 시간 복잡도는 `O(NM)`입니다.

문자열 매칭 알고리즘은 이 반복 비교를 줄입니다. 핵심 질문은 "이미 비교한 정보를 다음 위치에서 재사용할 수 있는가"입니다.

## KMP와 실패 함수

KMP는 패턴 내부에서 **현재 prefix 전체보다 짧으면서 접두사이자 접미사인 최대 길이**를 미리 계산합니다. 보통 이 배열을 `pi` 또는 failure function이라고 부릅니다.

예를 들어 `pattern = ababc`에서 앞부분 `abab`까지 봤다면, 접두사 `ab`와 접미사 `ab`가 일치합니다. 다음 문자가 틀렸을 때 패턴을 처음부터 다시 비교하지 않고, 이미 맞는 `ab` 길이만큼 상태를 유지할 수 있습니다.

`j`는 현재까지 맞은 패턴 길이입니다. 문자가 틀리면 `pi[j - 1]`로 되돌아가는데, 이 값은 "이미 맞은 접미사를 패턴의 접두사로 다시 쓸 수 있는 최대 길이"입니다.

## KMP로 패턴 찾기

`pi`를 계산한 뒤에는 텍스트를 왼쪽에서 오른쪽으로 한 번만 훑습니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <string>
#include <vector>
using namespace std;

vector<int> prefixFunction(const string& pattern) {
    int n = (int)pattern.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        pi[i] = j;
    }
    return pi;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> result;
    if (pattern.empty()) {
        return result;
    }

    vector<int> pi = prefixFunction(pattern);
    int matched = 0;
    for (int i = 0; i < (int)text.size(); ++i) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = pi[matched - 1];
        }
        if (text[i] == pattern[matched]) {
            ++matched;
        }
        if (matched == (int)pattern.size()) {
            result.push_back(i - matched + 1);
            matched = pi[matched - 1];
        }
    }
    return result;
}
```

빈 패턴은 이 API에서 등장 위치를 반환하지 않습니다. 매칭 후 실패 함수로 돌아가므로 겹친 등장도 찾습니다. 시간 복잡도는 `O(N + M)`입니다. `matched`가 증가하거나, 실패 함수로 감소하는 이동 전체가 선형 횟수 안에 묶이기 때문입니다.

## Z algorithm

Z algorithm은 문자열 `s`의 각 위치 `i`에 대해 `s[i...]`가 `s[0...]`와 얼마나 길게 일치하는지를 계산합니다. 이 값을 `z[i]`라고 합니다.

```text
s = aabcaab
z[4] = 3  // s[4..] = aab, 접두사 aab와 3글자 일치
```

구분자는 두 입력에 없는 문자로 고릅니다. 패턴을 텍스트에서 찾고 싶다면 `pattern + separator + text`를 만들고 Z 값을 계산합니다. 텍스트 영역에서 `z[i] >= pattern.size()`인 위치가 등장 위치입니다.

```cpp compile-check
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<int> zFunction(const string& s) {
    int n = (int)s.size();
    vector<int> z(n, 0);
    int left = 0;
    int right = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= right) {
            z[i] = min(right - i + 1, z[i - left]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > right) {
            left = i;
            right = i + z[i] - 1;
        }
    }
    return z;
}
```

Z algorithm도 `O(N)`입니다. 접두사와 일치하는 구간 `[left, right]`를 유지하면서, 이미 아는 구간 안에서는 값을 재사용합니다.

## Rolling Hash

Rolling Hash는 문자열을 숫자로 바꿔 부분 문자열 비교를 빠르게 하는 방법입니다. 접두사 해시를 전처리하면 임의 구간의 해시를 `O(1)`에 얻을 수 있습니다.

```cpp compile-check
#include <string>
#include <vector>
using namespace std;

const long long MOD = 1000000007LL;
const long long BASE = 911382323LL;

struct RollingHash {
    vector<long long> hash;
    vector<long long> power;

    explicit RollingHash(const string& s) {
        int n = (int)s.size();
        hash.assign(n + 1, 0);
        power.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            hash[i + 1] = (hash[i] * BASE + (unsigned char)s[i] + 1) % MOD;
            power[i + 1] = power[i] * BASE % MOD;
        }
    }

    long long get(int left, int right) const {
        long long value = (hash[right] - hash[left] * power[right - left]) % MOD;
        if (value < 0) {
            value += MOD;
        }
        return value;
    }
};
```

`get(left, right)`는 `0 <= left <= right <= s.size()`인 반열린 구간 `[left, right)`의 해시를 돌려줍니다. 같은 길이의 두 구간은 해시가 다르면 반드시 다르지만, 해시가 같으면 실제 문자를 더 확인해야 동등성을 확정할 수 있습니다.

### 이 코드에서 실제로 충돌하는 두 문자열

| 문자열 | 길이 | `get(0, 8)` |
| --- | ---: | ---: |
| `yxwvnird` | 8 | 104431294 |
| `inlchzgm` | 8 | 104431294 |

두 문자열은 서로 다릅니다. `BASE`와 `MOD`가 고정된 위 코드에서는 실행할 때마다 같은 충돌이 납니다. 따라서 임의의 입력에 대해 "충돌 확률이 `1 / MOD`"라고 단정할 수 없습니다. 확률을 말하려면 입력이나 해시 매개변수를 어떤 방식으로 무작위 선택하는지부터 정해야 합니다.

두 mod를 함께 써도 충돌 가능성이 사라지지는 않습니다. 정확한 결과가 필요하면 해시가 같은 후보의 원문을 직접 비교하거나, 문제에 맞는 KMP·Z 같은 정확 알고리즘을 선택합니다. [Princeton의 Rabin–Karp 구현](https://algs4.cs.princeton.edu/53substring/RabinKarp.java.html)도 해시 일치 후 문자를 직접 확인합니다.

직접 비교까지 포함하면 길이 `L`인 후보 한 쌍에 최악 `O(L)`이 듭니다. 해시 계산이 `O(1)`이라는 이유로 전체 동등성 확인도 항상 `O(1)`이라고 계산하면 안 됩니다.

## 무엇을 선택할까

| 문제 신호 | 우선 후보 |
| --- | --- |
| 한 패턴의 모든 등장 위치 | KMP 또는 Z |
| 접두사와 각 suffix의 일치 길이 | Z algorithm |
| 많은 부분 문자열 동등성 비교 | Rolling Hash |
| 여러 패턴을 동시에 찾기 | Trie, Aho-Corasick |
| 사전순 suffix 정렬, LCP 질의 | Suffix Array, LCP |

KMP와 Z는 정확한 선형 알고리즘입니다. Rolling Hash는 구현이 짧고 여러 구간 비교에 강하지만 충돌 가능성을 관리해야 합니다.

## 시간 복잡도

| 작업 | 시간 | 메모리 |
| --- | ---: | ---: |
| KMP 실패 함수 | `O(M)` | `O(M)` |
| KMP 검색 | `O(N + M)` | `O(M + 등장 수)` |
| Z function | `O(N)` | `O(N)` |
| Rolling Hash 전처리 | `O(N)` | `O(N)` |
| Rolling Hash 구간 해시 조회·비교 | `O(1)` | 전처리 배열 사용 |
| 해시가 같은 후보의 원문 확인 | 최악 `O(L)` | 추가 공간 `O(1)`로 비교 가능 |

입력 문자열이 여러 개인 경우에는 전체 길이 합을 기준으로 봐야 합니다. 테스트 케이스마다 큰 문자열을 복사하거나 `substr`를 많이 만들면 의도한 복잡도보다 느려질 수 있습니다.