접두·접미·LPS 배열 만들기

부분 일치 실패 뒤 재사용할 길이를 패턴 자체에서 계산합니다.

문자열 탐색이 실패했을 때 이미 비교한 정보를 모두 버릴 필요는 없습니다. 목표는 패턴의 접두·접미와 LPS의 의미를 직접 계산하는 것입니다. 문자열 인덱스와 반복 경계를 복습하세요.

개념과 약속

접두는 앞에서 시작하는 구간, 접미는 끝에서 끝나는 구간입니다. 진접두는 문자열 전체를 제외한 접두입니다. lps[i]는 pattern[0:i+1]에서 접두이면서 접미인 가장 긴 진접두의 길이입니다. ABAB의 접두 AB는 접미 AB와 같아 길이 2입니다.

다음 문자도 같으면 저장한 일치 길이 j를 하나 늘립니다. 다르면 j=lps[j-1]로 더 짧은 후보 경계를 사용합니다. 후보 길이가 0이 되거나 문자가 같아질 때까지 후보 경계를 줄여 가며 같은 문자를 확인합니다. 접두가 될 수 없는 길이를 하나씩 모두 시도하는 것보다 이미 계산한 경계를 따라갑니다.

자료구조·알고리즘 · 상태와 관계

같은 접두와 접미의 길이

ABAB의 전체를 제외한 가장 긴 공통 접두·접미는 AB입니다.

두 줄은 같은 문자열을 반복해 접두와 접미를 각각 보인 것입니다. 꺾인 선은 문자 구간의 묶음이며 이동 화살표가 아닙니다. 앞 AB와 뒤 AB의 내용이 같고 lps는 인덱스가 아니라 길이입니다.

손으로 상태 추적하기

패턴 ABABAC의 표입니다.

i	앞 구간	가장 긴 공통 진접두·접미	lps[i]
0	A	없음	0
1	AB	없음	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABA	ABA	3
5	ABABAC	없음	0

마지막 C에서 j=3의 B가 다르면 j=1, 다시 B가 다르면 j=0으로 되돌아갑니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. 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


print(prefix_function("ABABAC"))
print(prefix_function("AAAA"))
print(prefix_function(""))