KMP

어떤 문제를 푸는가

긴 텍스트 \(T\)(길이 \(N\)) 안에서 패턴 \(P\)(길이 \(M\))가 나타나는 모든 위치를
찾습니다. 단순 비교는 각 시작 위치마다 패턴을 처음부터 맞춰 보아 최악
\(O(NM)\)입니다. KMP는 이를 \(O(N + M)\)으로 줄입니다.

단순 검색의 낭비

T = aaaaab, P = aaab를 단순 비교하면, 한 위치에서 aaa까지 맞다가 b에서
어긋나면 텍스트 포인터를 한 칸만 뒤로 옮겨 처음부터 다시 봅니다. 하지만 우리는
이미 aaa가 맞았다는 정보를 알고 있습니다. 이 정보를 버리지 않는 것 이
KMP의 핵심입니다.

실패 함수 (failure / pi 배열)

패턴 자신에 대해, 각 접두사의 "진부분 접두사이면서 동시에 접미사 인 가장 긴
문자열의 길이"를 미리 계산합니다. 이를 \(\pi[i]\)라 합니다.

$$ \pi[i] = P[0..i] \text{의 접두사이면서 접미사인 가장 긴 진부분 문자열 길이} $$

예: P = ababa면 \(\pi = [0, 0, 1, 2, 3]\). abab의 접두=접미는 ab(길이 2),
ababa는 aba(길이 3)입니다.

이 값이 있으면, 매칭 중 어긋났을 때 "패턴의 어디로 점프해 다시 비교할지"를
즉시 알 수 있습니다. 텍스트 포인터는 절대 뒤로 가지 않습니다.

매칭 과정

텍스트를 왼쪽에서 오른쪽으로 한 번 훑습니다. 현재 패턴의 \(j\)개 글자가 맞아
있는 상태에서 다음 글자가 어긋나면, \(j\)를 \(\pi[j-1]\)로 줄여 "이미 일치하는
접두사"를 활용해 다시 시도합니다. \(j\)가 \(M\)에 도달하면 한 번의 출현입니다.

왜 선형인가

텍스트 포인터는 매 글자마다 한 번만 전진하니 \(O(N)\). 패턴 포인터 \(j\)는
어긋날 때 줄어들지만, 전진(맞을 때 +1)한 총량을 넘게 줄어들 수 없습니다.
따라서 \(j\)의 총 변화량도 \(O(N)\)입니다. 실패 함수 계산도 같은 논리로 \(O(M)\).
전체

$$ O(N + M) $$

핵심 직관

실패 함수는 패턴 내부의 자기 닮음(반복 구조) 을 미리 요약한 표입니다.
이 표 덕분에 어긋남이 생겨도 처음부터 다시 보지 않고, 이미 확보한 일치를
재활용합니다. 다음 강의에서 두 배열의 구현과 응용을 봅니다.

실패 함수 계산 (C++)

패턴과 텍스트의 검색이 같은 모양이라는 점이 KMP의 우아함입니다.

#include <bits/stdc++.h>
using namespace std;

vector<int> getPi(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);
    int j = 0;                       // 현재 일치한 접두사 길이
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];           // 어긋나면 더 짧은 접두=접미로 후퇴
        if (p[i] == p[j]) j++;
        pi[i] = j;
    }
    return pi;
}

텍스트에서 패턴 찾기 (C++)

vector<int> kmp(const string& t, const string& p) {
    vector<int> pi = getPi(p), res;
    int n = t.size(), m = p.size(), j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && t[i] != p[j])
            j = pi[j - 1];
        if (t[i] == p[j]) j++;
        if (j == m) {                // 패턴 한 번 완성
            res.push_back(i - m + 1);  // 0-based 시작 위치
            j = pi[j - 1];           // 겹치는 다음 출현을 위해 후퇴
        }
    }
    return res;                      // 모든 출현 시작 위치
}

매칭 루프가 실패 함수 계산과 거의 같음을 보세요. j = pi[j-1]로의 후퇴가
두 경우 모두 핵심입니다.

파이썬 구현

def get_pi(p):
    m = len(p)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = pi[j - 1]
        if p[i] == p[j]:
            j += 1
        pi[i] = j
    return pi

def kmp(t, p):
    pi = get_pi(p)
    res, j = [], 0
    for i, c in enumerate(t):
        while j > 0 and c != p[j]:
            j = pi[j - 1]
        if c == p[j]:
            j += 1
        if j == len(p):
            res.append(i - len(p) + 1)
            j = pi[j - 1]
    return res

흔한 함정

• 빈 패턴/패턴이 더 긴 경우 — 경계를 확인. \(M = 0\)이나 \(M > N\) 처리.
• 출현 후 후퇴 누락 — j == m 직후 j = pi[j-1]을 빼면 다음 출현을
  놓치거나(겹치는 경우) 인덱스가 꼬입니다.
• while vs if — 어긋남 처리는 반드시 while(여러 단계 후퇴 가능).
• 인덱스 0/1 기준 — 출력 형식(0-based/1-based)을 문제에 맞추기.

응용 패턴

• 모든 출현 위치 / 출현 횟수 — 위 구현 그대로.
• 문자열의 최소 주기 — 길이 \(n\), \(\pi[n-1] = k\)일 때, \(n - k\)가 주기
  후보. \(n \% (n - k) == 0\)이면 그 문자열은 길이 \(n-k\) 패턴의 반복입니다.
• 접두사이면서 접미사인 모든 길이 — \(\pi[n-1]\)에서 시작해 \(\pi\)를 따라
  체인을 타고 내려가며 모두 수집.
• 두 문자열 이어 붙여 부분 문자열/회전 판정 — P + '#' + T 또는 T + T.
• 아호-코라식의 토대 — 여러 패턴 동시 검색으로 확장(상위 단원).

실패 함수라는 "패턴의 자기 구조 요약" 하나만 정확히 이해하면, KMP 본체와
다양한 문자열 응용이 자연스럽게 따라옵니다.