한양과기고 에듀테크 수업도구 대시보드

KMP 문자열 검색 (Knuth–Morris–Pratt)

긴 텍스트 안에서 짧은 패턴이 나타나는 위치를 찾는 문제다. 단순 방법은 불일치가 날 때마다 텍스트 포인터를 한 칸 뒤로 되돌려 처음부터 다시 비교한다 — 최악의 경우 O(n·m). KMP는 실패 함수(LPS 배열)를 미리 계산해 두어, 이미 일치했던 부분은 다시 보지 않고 패턴만 앞으로 점프시킨다. 텍스트 포인터는 절대 뒤로 가지 않는다 → O(n + m).

1. 실패 함수 (LPS: Longest Proper Prefix that is also Suffix)

패턴의 각 위치 i에 대해, 패턴[0..i]의 접두사이면서 동시에 접미사인 가장 긴 문자열의 길이를 저장한다. 불일치가 나면 이 값만큼 패턴이 스스로 겹쳐질 수 있다는 뜻이라, 그 지점부터 다시 비교하면 된다.

패턴 (pattern)

파란 칸을 클릭하면 그 위치까지의 접두사=접미사가 무엇인지 표시된다.

2. 탐색 시각화 — 텍스트 포인터는 되돌아가지 않는다

텍스트 (text)

패턴 (pattern)

패턴을 입력하고 ▶ 한 단계를 눌러 시작하세요.

비교 횟수 (KMP)

비교 횟수 (단순 탐색)

찾은 위치 수

주황 칸 = 지금 비교 중 · 초록 칸 = 일치 누적 · 빨강 칸 = 불일치 · 파랑 = 패턴 발견. 불일치가 나면 패턴이 LPS[j-1] 만큼만 오른쪽으로 미끄러진다.

3. 왜 O(n + m)인가

단순 탐색

불일치 시 텍스트 포인터를 시작 위치 + 1로 되돌린다. 이미 본 문자를 또 본다. "AAAA...AB" 같은 입력에서 O(n·m).

KMP

텍스트 포인터 i는 단조 증가만 한다. 불일치 시 패턴 포인터 j만 LPS[j-1]로 감소. 전체 O(n) + LPS 계산 O(m).

LPS의 의미

패턴[0..j-1]이 텍스트와 일치한 상태에서 패턴[j]가 어긋나면, 이미 맞은 접미사 = 접두사 부분은 다시 안 봐도 된다.

활용

텍스트 편집기 찾기, DNA 서열 검색, 네트워크 침입 탐지(패킷 시그니처 매칭), strstr 계열 구현의 기초.

4. 파이썬 구현

# 실패 함수(LPS) 계산 — O(m)
def build_lps(p):
    lps = [0] * len(p)
    length = 0              # 직전까지 일치한 접두사 길이
    for i in range(1, len(p)):
        while length > 0 and p[i] != p[length]:
            length = lps[length - 1]   # 더 짧은 접두사로 후퇴
        if p[i] == p[length]:
            length += 1
        lps[i] = length
    return lps

# KMP 검색 — O(n)
def kmp_search(text, p):
    lps = build_lps(p)
    j = 0                     # 패턴 포인터
    for i in range(len(text)):   # i(텍스트 포인터)는 되돌아가지 않음
        while j > 0 and text[i] != p[j]:
            j = lps[j - 1]
        if text[i] == p[j]:
            j += 1
        if j == len(p):
            yield i - j + 1       # 매칭 시작 인덱스
            j = lps[j - 1]

핵심은 두 함수가 똑같은 while j > 0 and ...: j = lps[j-1] 후퇴 로직을 쓴다는 점이다. 실패 함수 자체가 "패턴을 패턴에서 검색"하는 KMP다.