🔍 KMP (Knuth-Morris-Pratt) 문자열 탐색 알고리즘 정리

KMP는 문자열 검색 시, 이미 비교했던 내용을 다시 비교하지 않도록 최적화된 알고리즘이다.
문자열을 탐색하면서 생기는 중복 비교를 피하기 위해 LPS 배열이라는 구조를 사용한다.

---

💡 왜 KMP가 필요할까?

기존 브루트포스 방식은 문자열이 맞다가 틀리면 처음부터 다시 비교함 → 비효율적
KMP는 틀린 순간, "패턴의 어디부터 다시 비교하면 되는지"를 LPS 배열로 알려준다.

---

📌 핵심 키워드: LPS (Longest Prefix Suffix)

• LPS[i]는 0부터 i까지의 부분 문자열에서,
  접두사(prefix) == 접미사(suffix)가 일치하는 최대 길이를 의미함
• 단, 전체 문자열과 동일한 경우는 제외한다 (즉, 겹치지 않아야 함)

예시:
패턴 = "abab"

인덱스	부분 문자열	LPS 값	설명
0	a	0	첫 글자라 없음
1	ab	0	a ≠ b
2	aba	1	a == a
3	abab	2	ab == ab

→ 최종 LPS 배열: [0, 0, 1, 2]

---

🧠 KMP 알고리즘 동작 흐름

1. 패턴에 대해 LPS 배열 생성 (시간복잡도: O(M))
2. 텍스트를 순회하면서 패턴과 비교 시작
   • 매칭 성공 시 → 다음 문자 비교
   • 매칭 실패 시 → LPS 정보를 참고하여 점프 후 비교 재시작

---

⏱ 시간복잡도

• 전처리 (LPS 계산): O(M)
• 탐색 (텍스트 순회): O(N)
• 총합: O(N + M)
  (N: 텍스트 길이, M: 패턴 길이)

→ 시간복잡도가 항상 일정하고 안정적임

---

✅ KMP 코드 예제 (C언어 기준)

#include <stdio.h>
#include <string.h>

// LPS 배열을 만드는 함수
void computeLPSArray(char* pattern, int M, int* lps) {
    int len = 0;  // 이전까지 일치한 접두사/접미사 길이
    lps[0] = 0;   // 항상 0부터 시작
    int i = 1;

    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
                // i는 증가 안 함
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// KMP 매칭 함수
void KMPSearch(char* pattern, char* text) {
    int M = strlen(pattern);
    int N = strlen(text);

    int lps[M];
    computeLPSArray(pattern, M, lps);

    int i = 0; // 텍스트 인덱스
    int j = 0; // 패턴 인덱스
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == M) {
            printf("패턴 발견 위치: %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

사용 예시

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    KMPSearch(pattern, text);
    return 0;
}

출력

패턴 발견 위치: 10

---

🧪 실무 적용 예시

• 검색창 Ctrl + F 기능
• 텍스트 에디터 문자열 검색
• 로그 데이터, 자연어 처리에서 특정 키워드 추출
• 백엔드 필터링, 자동완성, 실시간 검색 등에서도 기반 로직으로 사용 가능

---

💬 마무리

KMP는 단순히 알고리즘 대회용이 아니라,
실무에서도 성능 최적화와 직결되는 핵심 알고리즘이다.
구조는 단순하지만, 아이디어는 정말 강력하다.

“반복을 피하자” 이 철학이 담긴 알고리즘, 그게 바로 KMP다.