KMP 알고리즘을 DFA(오토마타) 관점에서 이해하기

문자열 검색 알고리즘인 KMP (Knuth-Morris-Pratt)는 단순한 비교가 아니라, 오토마타(DFA)처럼 상태를 가지며 동작하는 구조로도 이해할 수 있습니다. 이 글에서는 최대한 쉽게 그 원리를 풀어보겠습니다.

---

🔍 1. KMP는 뭘 하려는 걸까?

문자열 T에서 특정 패턴 P를 효율적으로 찾기 위한 알고리즘입니다.
단순 비교는 느릴 수 있으니, 이미 매칭된 정보를 활용해서 뒤로 돌아가지 않고 매칭하는 것이 핵심입니다.

---

🤖 2. 오토마타처럼 동작한다고?

KMP는 다음과 같은 구조를 가집니다:

• 상태(State): 지금까지 맞은 패턴 접두사의 길이
• 입력(Input): 텍스트에서 들어오는 문자
• 전이 함수(Transition): 다음 상태로 이동하거나 실패 시 fallback

예를 들어 상태 3이면, 패턴 P의 처음 3글자 P[0:3]까지 매칭된 상태입니다. 다음 입력 문자에 따라 상태가 변화하게 되죠.

---

📐 3. 실패 함수(π 배열)

실패 함수는 매칭이 실패했을 때 어디서 다시 시작할지를 알려주는 배열입니다.
이는 오토마타에서 fallback 경로를 의미합니다.

예) 패턴 P = "ababaca"일 때
π = [0, 0, 1, 2, 3, 0, 1]

예를 들어 상태 4에서 실패했다면, π[4] = 3 → 다시 상태 3부터 시작하는 것입니다.

---

🧠 4. 전이 오토마타 (DFA 구성 예시)

패턴 P = ababaca에 대한 KMP DFA를 아래와 같이 표현할 수 있습니다.

stateDiagram-v2
    [*] --> S0

    S0 --> S1: a
    S0 --> S0: b/c

    S1 --> S2: b
    S1 --> S1: a
    S1 --> S0: c

    S2 --> S3: a
    S2 --> S1: b
    S2 --> S0: c

    S3 --> S4: b
    S3 --> S1: a
    S3 --> S0: c

    S4 --> S5: a
    S4 --> S2: b
    S4 --> S0: c

    S5 --> S6: c
    S5 --> S3: a
    S5 --> S0: b

    S6 --> S7: a
    S6 --> S0: b/c

    S7 --> [*]: (Match)

각 상태는 "지금까지 얼마나 매칭됐는지"를 기억하고, 다음 입력에 따라 어디로 갈지를 전이합니다. 실패 시에는 π 배열 값에 따라 되돌아가게 됩니다.

---

📌 요약

• KMP는 오토마타처럼 동작하는 문자열 검색 알고리즘입니다.
• 각 상태는 패턴 접두사 매칭 상태를 의미하며, 입력 문자에 따라 전이합니다.
• 실패 함수(π 배열)는 오토마타의 fallback 경로로 작용하여 불필요한 비교를 줄입니다.

---