KMP의 실패 전이와 겹치는 일치

텍스트를 되감지 않고 LPS 길이를 따라 부분 일치를 재사용합니다.

단순 탐색에서는 한 문자 비교에 실패한 뒤 다음 시작점에서 같은 문자를 다시 읽을 수 있습니다. 목표는 텍스트 위치를 되돌리지 않는 KMP의 상태와 전체 일치 후 처리까지 설명하는 것입니다. LPS 의미를 먼저 이해하세요.

개념과 약속

텍스트 인덱스 i는 오른쪽으로만 진행하고, j는 지금까지 일치한 패턴 접두의 길이입니다. 현재 문자가 다르면 j=lps[j-1]로 일치한 구간의 접미이기도 한 짧은 접두를 남깁니다. 같은 텍스트 문자와 짧아진 패턴 위치를 다시 비교합니다. 같으면 j를 하나 늘립니다.

j가 패턴 길이 m이 되면 시작 i-m+1을 기록합니다. 그 뒤 j를 0으로 무조건 지우지 않고 lps[m-1]로 되돌려 겹치는 일치를 찾습니다. 빈 패턴은 본문의 명세대로 모든 경계를 반환해 인덱스 접근 전에 처리합니다.

손으로 상태 추적하기

text=ABABABA, pattern=ABA, lps=[0,0,1]입니다.

텍스트 i	문자	처리 뒤 j	발견
0	A	1	없음
1	B	2	없음
2	A	3→1	시작 0
3	B	2	없음
4	A	3→1	시작 2
5	B	2	없음
6	A	3→1	시작 4

전체 일치 뒤 끝의 A를 다음 시작의 A로 재사용합니다.

부분 불일치에서 같은 문자를 다시 비교하기

text=ABABABAC, pattern=ABABAC, lps=[0,0,1,2,3,0]을 보겠습니다. 여기서 j는 이번 문자 처리 전까지 맞춘 접두의 길이입니다. i=5에서 패턴[5]는 C지만 텍스트[5]는 B입니다.

i·텍스트 문자	처리 전 j	비교·실패 전이	처리 뒤 j·발견
0·A	0	A=패턴[0]	1
1·B	1	B=패턴[1]	2
2·A	2	A=패턴[2]	3
3·B	3	B=패턴[3]	4
4·A	4	A=패턴[4]	5
5·B	5	B≠C → j=lps[4]=3; 같은 B를 패턴[3]=B와 재비교	4
6·A	4	A=패턴[4]	5
7·C	5	C=패턴[5]	전체 길이 6 → 시작 2 기록 → j=lps[5]=0

실패 직전 맞춘 ABABA의 접미 ABA는 패턴의 접두이기도 합니다. 따라서 앞의 두 문자를 새 시작 후보에서 제외하고 길이 3을 남길 수 있습니다. j를 단순히 하나 줄여 4로 두면 ABAB이 접미라는 근거가 없고, 무조건 0으로 지우면 이미 확인한 겹침을 잃습니다.

텍스트 문자마다 j를 늘리는 j += 1은 최대 한 번이므로 총 증가량은 n 이하입니다. 실패 전이와 전체 일치 뒤의 전이는 j를 낮추며 j는 음수가 되지 않습니다. 따라서 전체 감소량도 전체 증가량 이하이고, 엄격히 감소하는 실패 전이의 횟수도 O(n)입니다. 같은 문자에서 여러 번 후퇴하더라도 이 총량을 중복 계산하지 않으므로 전처리 O(m)와 합쳐 O(n+m)입니다. 실제 Python 문자열의 문자 처리 비용은 본문의 코드 포인트 모델을 사용합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

def prefix_function(pattern):
    prefix = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j and pattern[i] != pattern[j]:
            j = prefix[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        prefix[i] = j
    return prefix


def kmp_matches(text, pattern):
    if not pattern:
        return list(range(len(text) + 1))
    prefix = prefix_function(pattern)
    matches, j = [], 0
    for i, character in enumerate(text):
        while j and character != pattern[j]:
            j = prefix[j - 1]
        if character == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = prefix[j - 1]
    return matches


print(kmp_matches("ABABABA", "ABA"))
print(kmp_matches("AAAA", "AA"))
print(kmp_matches("가나다가나", "가나"))
print(kmp_matches("AB", ""))