카테고리 없음

KMP 알고리즘: 실패 함수를 이용한 고속 문자열 검색 완벽 가이드

머니지니87 2026. 4. 11. 21:11

방대한 텍스트 데이터 내에서 특정 단어나 패턴을 찾는 기능은 검색 엔진, 유전체 분석, 텍스트 에디터 등 수많은 소프트웨어에서 핵심적으로 작동합니다. 가장 단순한 방식인 브루트 포스(Brute Force) 검색은 본문의 한 칸씩 옆으로 이동하며 패턴을 대조하느라 시간이 너무 오래 걸린다는 치명적인 단점이 있습니다. 이러한 비효율을 획기적으로 개선하여 중복되는 비교를 과감히 생략하는 기법이 바로 KMP(Knuth-Morris-Pratt) 알고리즘입니다. 본 포스팅에서는 KMP의 핵심인 실패 함수의 원리와 작동 매커니즘을 2,500자 이상의 상세한 분석으로 파헤쳐 보겠습니다.

1. 기존 문자열 검색의 한계와 KMP의 등장 배경

기본적인 문자열 검색 방식은 본문 문자열의 인덱스를 하나씩 증가시키며 패턴과 대조합니다. 만약 본문이 "AAAAAB"이고 패턴이 "AAAB"라면, 네 번째 글자에서 틀렸을 때 다시 본문의 두 번째 칸부터 처음부터 대조를 시작합니다. 이는 이미 확인한 정보를 버리고 다시 시작하는 꼴이 되어, 본문의 길이를 $N$, 패턴의 길이를 $M$이라 할 때 최악의 경우 $O(N \times M)$의 시간 복잡도를 가집니다. KMP는 이 '이미 확인한 정보'를 활용해 본문의 포인터를 뒤로 되돌리지 않고도 검색을 이어갑니다.

1-1. 이미 알고 있는 정보를 활용하는 지혜

KMP 알고리즘의 핵심 철학은 "일치하지 않는 문자를 만났을 때, 본문의 포인터를 되돌리지 말고 패턴의 포인터를 적절한 위치로 점프시키자"는 것입니다. 이를 가능하게 하려면 패턴 내부에 존재하는 반복되는 구조를 미리 파악해야 합니다. 이 반복 구조를 수치화한 것이 바로 실패 함수입니다.

2. KMP의 심장: 실패 함수(Failure Function, pi 배열)

실패 함수란 패턴 내에서 접두사(Prefix)와 접미사(Suffix)가 일치하는 가장 긴 길이를 미리 계산해둔 표입니다. 이를 통해 불일치가 발생했을 때, 우리가 어디까지는 이미 일치했음을 확신하고 그 다음부터 비교를 재개할 수 있는지를 알려줍니다.

2-1. 실패 함수의 계산 매커니즘

패턴 "ABCAB"를 예로 들어보겠습니다. "A"의 접두사/접미사 일치 길이는 0입니다. "AB"도 0입니다. "ABC"도 0입니다. 하지만 "ABCA"의 경우 접두사 "A"와 접미사 "A"가 일치하므로 길이는 1이 됩니다. 마지막으로 "ABCAB"는 접두사 "AB"와 접미사 "AB"가 일치하여 길이는 2가 됩니다. 만약 "ABCAB"를 검색하다가 마지막 'B' 다음에 틀린다면, 우리는 이미 앞의 "AB"가 일치함을 알고 있으므로 패턴의 2번 인덱스(세 번째 글자)부터 바로 비교를 시작하면 됩니다.

3. KMP 알고리즘의 탐색 과정과 시간 복잡도

탐색 단계에서도 실패 함수를 동일하게 적용합니다. 본문 포인터 $i$와 패턴 포인터 $j$가 움직일 때, 문자가 일치하면 두 포인터를 모두 증가시킵니다. 만약 불일치가 발생하면 $i$는 가만히 두고, $j$만 실패 함수 값($pi[j-1]$)으로 이동시킵니다. 이 방식 덕분에 본문 전체를 단 한 번만 훑고도 검색이 종료됩니다.

3-1. $O(N + M)$의 압도적 성능

KMP 알고리즘은 패턴의 실패 함수를 만드는 데 $O(M)$, 본문을 탐색하는 데 $O(N)$의 시간이 소요되어 전체적으로 $O(N + M)$이라는 선형 시간 복잡도를 달성합니다. 이는 본문의 길이가 수백만 자에 달하더라도 패턴의 길이만큼의 추가 시간만 들이면 검색이 가능하다는 것을 의미하며, 문자열 처리 알고리즘 중 가장 효율적인 기법으로 손꼽힙니다.

4. 실무에서의 활용 및 구현 시 주의사항

KMP는 단순 검색을 넘어 데이터 압축, 침입 탐지 시스템(IDS)의 패턴 매칭, 그리고 유전체 서열의 중복 구간 탐지 등에서 중추적인 역할을 합니다. 구현 시 주의할 점은 인덱스 관리입니다. 0번 인덱스부터 시작하는 배열 특성상 $j-1$을 참조할 때 인덱스 범위를 벗어나지 않도록 세심한 조건문 처리가 필요합니다.


# KMP 알고리즘 실패 함수(pi) 계산 Python 구현
def compute_pi(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j-1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    return pi
[KMP 알고리즘 핵심 요약]
1. 원리: 이미 비교한 본문 정보를 버리지 않고 실패 함수를 통해 비교 위치를 최적화합니다.
2. 핵심: 접두사와 접미사의 일치 길이를 활용해 불필요한 중복 대조를 원천 차단합니다.
3. 성능: $O(N+M)$의 선형 시간을 보장하며 대규모 텍스트 처리에 최적화된 기법입니다.