KMP 알고리즘

직접 해보세요

python

KMP 알고리즘

레슨 1 · 파이썬 알고리즘 플래티넘

KMP 알고리즘 (Knuth-Morris-Pratt)

KMP는 텍스트에서 패턴 문자열을 **O(n+m)**에 찾는 알고리즘이에요. 파이배열(실패 함수)을 이용해 이미 확인한 부분을 건너뜁니다.

파이배열 (Pi Array, Failure Function)

pi[i] = 패턴의 0~i 부분 문자열에서 접두사 == 접미사인 최장 길이

python

def build_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

# 예시: "ABAABAB"
# pi = [0, 0, 1, 1, 2, 3, 2]
print(build_pi("ABAABAB"))

# 예시: "AABAA"
# pi = [0, 1, 0, 1, 2]
print(build_pi("AABAA"))

KMP 탐색

python

def kmp(text, pattern):
    n, m = len(text), len(pattern)
    pi = build_pi(pattern)
    result = []   # 패턴이 등장하는 시작 인덱스 목록

    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]         # 파이배열로 점프

        if text[i] == pattern[j]:
            j += 1

        if j == m:                # 패턴 완전 매칭
            result.append(i - m + 1)
            j = pi[j - 1]         # 다음 탐색 위치

    return result

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp(text, pattern))   # [10]

시간복잡도

단계	복잡도
파이배열 생성	O(m)
탐색	O(n)
전체	O(n + m)

나이브 탐색 O(n×m)보다 훨씬 빠릅니다.

정리

KMP: 파이배열로 매칭 실패 시 되돌아갈 위치 계산
시간복잡도 O(n+m)
파이배열 = 접두사이면서 접미사인 최장 길이