KMP 알고리즘에서 pi 배열은 이미 비교한 문자열 정보를 버리지 않기 위한 장치입니다. 문자열 매칭이 느려지는 이유는 불일치가 날 때 앞에서 맞았던 부분을 다시 비교하기 때문입니다.
pi 배열의 핵심은 패턴의 앞부분과 뒷부분이 얼마나 겹치는지 미리 저장해 두는 것입니다. 이 값을 알면 실패 후 어디로 돌아가야 할지 바로 정할 수 있습니다.
KMP 알고리즘이 해결하려는 문제
문자열 text 안에서 pattern을 찾는 가장 단순한 방법은 모든 시작 위치에서 pattern을 처음부터 비교하는 것입니다. 하지만 앞부분이 많이 겹치는 문자열에서는 같은 비교가 반복됩니다.
예를 들어 pattern이 ABABAC라면, ABABA까지 맞고 마지막 C에서 틀렸을 때 처음부터 다시 비교하는 것은 낭비입니다. 이미 ABABA 안에는 다시 활용할 수 있는 접두사와 접미사의 겹침이 있습니다.
pi 배열의 의미
pi[i]는 pattern[0..i] 구간에서, 전체 문자열 자기 자신은 제외하고, 접두사이면서 접미사인 가장 긴 길이입니다. 말은 어렵지만 질문은 단순합니다. ‘여기까지 봤을 때 앞부분과 뒷부분이 얼마나 같나?’입니다.
pattern = ABABAC
A -> pi = 0
AB -> pi = 0
ABA -> pi = 1 (A)
ABAB -> pi = 2 (AB)
ABABA -> pi = 3 (ABA)
ABABAC -> pi = 0불일치가 났을 때 왜 다시 비교하지 않을까
text와 pattern을 비교하다가 pattern[j]에서 틀렸다고 해봅니다. 이때 pattern[0..j-1]은 이미 text와 맞았습니다. pi[j-1]은 이 맞은 부분 안에서 다시 후보가 될 수 있는 가장 긴 접두사 길이를 알려줍니다.
그래서 j를 0으로 되돌리지 않고 pi[j-1]로 줄입니다. 이게 KMP가 비교 정보를 재사용하는 핵심입니다.
pi 배열 계산 코드
def build_pi(pattern: str) -> list[int]:
pi = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi문자열 검색에서 쓰는 방법
def kmp_search(text: str, pattern: str) -> list[int]:
pi = build_pi(pattern)
result = []
j = 0
for i, ch in enumerate(text):
while j > 0 and ch != pattern[j]:
j = pi[j - 1]
if ch == pattern[j]:
if j == len(pattern) - 1:
result.append(i - len(pattern) + 1)
j = pi[j]
else:
j += 1
return resultpi 배열을 이해할 때 자주 하는 착각
- pi 배열은 text가 아니라 pattern에 대해 만든다
- pi 값은 일치한 전체 길이가 아니라 접두사와 접미사의 겹침 길이다
- 불일치 후 무조건 0으로 가는 것이 아니라 pi를 따라 짧은 후보로 이동한다
- KMP는 외워서 쓰는 코드보다 되돌아가는 의미를 이해해야 오래 남는다
시간 복잡도
pi 배열을 만드는 데 O(M), text를 훑는 데 O(N)이 걸립니다. while이 중첩되어 보여도 j는 증가와 감소를 반복할 뿐 전체적으로 선형 범위 안에서 움직입니다. 그래서 전체 시간 복잡도는 O(N+M)입니다.
정리
KMP 알고리즘에서 pi 배열은 불일치 후 다시 비교하지 않기 위한 지도입니다. prefix와 suffix의 겹침 길이를 알고 있기 때문에, 이미 확인한 정보를 버리지 않고 다음 후보 위치로 이동할 수 있습니다.
정의와 증명 흐름은 CP-Algorithms prefix function 문서를 기준으로 확인할 수 있습니다. 알고리즘 사고법은 투 포인터 알고리즘 글과 함께 읽으면 비교 감각이 좋아집니다.
