Z 함수는 문자열의 각 위치에서 시작하는 접미가 문자열 전체의 접두와 얼마나 오래 일치하는지를 배열에 기록합니다. z[i]를 구하면 위치 i의 문자를 무조건 처음부터 다시 비교하는 대신, 이미 계산한 접두 일치 구간을 거울처럼 재사용할 수 있습니다. 핵심은 “현재까지 가장 오른쪽까지 확인한 일치 구간”을 [l, r) 반열린 구간으로 유지하는 것입니다. r은 이미 비교가 끝난 다음 위치이므로 i < r이면 일부 비교 결과를 알고 있고, i >= r이면 새로 확인해야 합니다.
z[0]은 정의가 구현마다 다를 수 있습니다. 여기서는 참조 문서처럼 0으로 둡니다. 문자열을 바이트 배열로 볼지 코드 포인트 배열로 볼지는 KMP와 마찬가지로 API가 먼저 결정해야 합니다.
Z 값의 정의
길이 n인 문자열 s에서 z[i]는 s[i..]의 접두와 s[0..]의 최대 공통 접두 길이입니다. 예를 들어 s = aabcaabxaaaz에서 i=4의 suffix는 aabxaaaz이고 문자열 접두 aab...와 aab까지 일치하므로 z[4]=3입니다. i=1에서는 ab...와 aab...의 첫 글자가 달라 z[1]=1 같은 식으로 계산합니다.
Z 값은 “위치에서 패턴이 시작한다”는 의미로도 읽을 수 있지만, 일반 문자열의 접두와 비교한 값입니다. 따라서 패턴 검색에서 텍스트의 모든 위치를 직접 비교하는 것이 아니라, 패턴을 결합 문자열의 접두로 만들어 z[i] == |pattern|을 찾는 방식이 가능합니다.
그림을 글로 읽기
- 접두 [0,r-l): 기준 문자열
- 일치 구간 [l,r): 같은 내용
- z[i-l]: 거울 좌표의 값
- min(z[i-l], r-i): 안전한 초기값
- 접두 [0,r-l) → 일치 구간 [l,r): 문자열 내용이 일치
- 일치 구간 [l,r) → z[i-l]: i-l 좌표 대응
- z[i-l] → min(z[i-l], r-i): r 경계로 제한
반열린 구간 상태
알고리즘은 지금까지 발견한 일치 구간 중 오른쪽 끝이 가장 큰 하나를 [l,r)로 저장합니다. s[l..r)와 s[0..r-l)가 일치한다는 불변식이 있습니다. 현재 위치 i가 r 이상이면 알고 있는 구간 바깥이므로 z[i]=0에서 문자 비교를 시작합니다. 일치가 생겨 i+z[i] > r이면 [l,r)를 새 구간으로 교체합니다.
i < r이면 i는 기존 구간 안입니다. 이때 i-l은 접두 쪽에서 대응하는 위치입니다. 기존 구간의 내용이 같으므로 z[i-l]만큼은 재사용할 수 있지만, 그 값이 현재 구간의 오른쪽 경계를 넘어갈 수 있습니다. 따라서 초기값은 min(z[i-l], r-i)입니다. 그 뒤 i+z[i]가 r에 도달하면 미지의 문자 영역을 직접 비교해 확장합니다.
이때 [l,r)를 닫힌 구간 [l,r]처럼 다루면 r 위치를 이미 검사한 것으로 오해하게 됩니다. 구현의 비교 조건은 i+z[i] < n이고, 현재 구간 내부에서 안전하게 아는 끝은 r-1까지입니다.
구간 복사와 중간 상태
문자열 aaaabaa를 예로 들면 앞쪽 aaaa 계열 일치로 [l,r)가 오른쪽까지 확장됩니다. 마지막 위치 i=6이 기존 [5,7) 안에 있다고 합시다. 대응 좌표는 i-l=1이고 z[1]=3일 수 있지만, 현재 구간에서 r-i=1만 확실합니다. 그래서 초기값은 min(3,1)=1입니다. 3을 그대로 복사하면 s[7] 이후의 문자를 이미 일치한다고 가정하는 오류가 됩니다.
동작을 숫자로 적으면 다음과 같습니다.
| i | 기존 [l,r) |
대응 i-l |
z[i-l] |
r-i |
초기 z[i] |
|---|---|---|---|---|---|
| 6 | [5,7) |
1 | 3 | 1 | 1 |
이 문자열은 길이가 7이므로 초기값 1을 얻은 뒤 i+z[i]=7에서 입력 끝에 도달하여 비교를 종료합니다. 더 긴 문자열에서 같은 [5,7) 상태를 만났다면 경계 밖 문자를 실제 비교하고, 일치할 때만 값을 늘릴 수 있습니다. 이 구체적인 min이 Z 알고리즘에서 가장 중요한 안전장치입니다.
선형 시간의 이유
각 위치마다 while 루프가 있어도 매 비교가 중복되어 전체가 제곱 시간이 되지는 않습니다. 새로운 문자 비교가 성공해 while 루프를 한 번 진행할 때, 그 비교는 오른쪽 경계 r을 앞으로 밀어야 합니다. r은 문자열 끝을 넘을 수 없으므로 전체 확장 비교 횟수는 O(n)입니다. 위치를 훑는 바깥 루프도 O(n)이므로 총 시간은 O(n), 배열 저장은 O(n)입니다.
반대로 처음부터 각 i에서 접두와 suffix를 다시 비교하는 순진한 구현은 aaaaa처럼 동일 문자가 반복될 때 같은 비교를 반복합니다. Z의 구간 재사용은 문자를 건너뛰는 휴리스틱이 아니라, 이미 [l,r) 내부에서 확정한 동일성을 좌표 변환해 초기값으로 쓰는 정확한 재사용입니다.
구현 구조와 경계
z_function(s):
z = [0] * len(s)
l = r = 0
for i in 1 .. len(s)-1:
if i < r:
z[i] = min(r - i, z[i-l])
while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
[l,r)가 비어 있는 초기 상태 [0,0)에서는 어떤 i>=r도 기존 구간을 사용하지 않습니다. i+z[i] == r이면 새 구간이 오른쪽으로 늘지 않았으므로 [l,r)를 바꿀 필요가 없습니다. >일 때만 갱신합니다. 이 비교를 >=로 바꿔도 값이 틀리지 않는 경우가 있지만, 상태의 의미와 불필요한 갱신을 흐리므로 반열린 계약에 맞춰 >로 고정하는 편이 안전합니다.
패턴 검색과 구분자
패턴 p, 텍스트 t가 있을 때 s = p + sep + t를 만듭니다. sep는 두 입력에 모두 없는 단일 토큰이어야 합니다. 결합 문자열에서 텍스트 위치 x에 해당하는 인덱스는 x + |p| + 1입니다. 이 위치의 Z 값이 |p|이면 패턴이 텍스트 x에서 시작합니다. 예를 들어 p=aba, t=ababa이면 aba#ababa에서 텍스트 위치 0과 2의 대응 Z 값이 3이므로 두 출현을 보고합니다.
구분자 없이는 패턴 접두가 결합 문자열을 넘어 텍스트까지 계속 일치할 수 있어, Z 값이 “패턴 전체 일치”인지 “패턴 접두 뒤의 텍스트까지 우연히 일치”인지 경계가 흐려집니다. 구분자가 실제 입력에 나올 수 있으면 결합 방식의 전제가 사라집니다. 입력 알파벳 바깥 토큰을 사용할 수 없으면 별도 토큰 배열, 길이와 종류가 보존되는 구조, 또는 직접 스트리밍 검색을 선택해야 합니다. 빈 패턴의 결과 위치도 별도 계약입니다.
결합 문자열을 만들면 패턴과 텍스트를 포함한 O(|p|+|t|) 저장이 필요합니다. 정적 배치 검색에서 단순하고 검증하기 쉽지만, 소켓 스트림을 무한히 읽는 경우에는 매번 결합 문자열을 만들기보다 KMP 상태 또는 다른 스트리밍 구조가 자연스럽습니다.
반복 주기 판정
길이 n인 문자열에서 후보 블록 길이 i가 전체 반복 블록이 되려면 두 조건을 함께 적용합니다. 첫째 n % i == 0이어야 블록이 정수 번 반복됩니다. 둘째 i + z[i] == n이어야 위치 i부터 끝까지가 전체 접두와 일치합니다. 후보를 작은 순서로 살펴 처음 만족하는 i를 최소 반복 블록 길이로 택할 수 있습니다.
aaaa에서는 i=1, z[1]=3, 1+3=4이고 4 % 1=0이므로 a가 네 번 반복됩니다. abac에서 i=2는 4 % 2=0이지만 z[2]=0이므로 조건을 충족하지 않습니다. 나눗셈만 확인하면 길이만 맞는 서로 다른 블록을 반복으로 오판합니다. 반대로 i+z[i] == n만 확인하면 전체 길이가 블록 배수인지 보장하지 못합니다.
append와 온라인 경계
정적 Z 계산은 입력 문자열 전체가 고정되어 있다는 전제에서 [l,r) 경계를 관리합니다. 문자열 뒤에 문자를 append하면 새 문자는 기존 끝을 넘어가므로, 이전 계산에서 끝까지 닿지 않았던 위치의 Z 값은 그대로일 수 있지만 옛 끝에 도달해 멈춘 값은 늘어날 수 있습니다. 그러므로 기존 배열에 새 위치 하나만 계산해 붙이면 완전한 온라인 Z 갱신이 되지 않습니다.
가장 작은 반례는 aaa입니다. 기존 z는 [0,2,1]이고, 옛 길이는 3입니다. i+z[i] == 3인 위치 1과 2가 모두 옛 경계에 닿아 있습니다. 마지막에 a를 붙여 aaaa가 되면 위치 1은 2→3, 위치 2는 1→2로 늘어납니다. 즉 i+z[i] < oldLength인 값은 새 문자만으로 연장될 수 없지만, ==인 모든 값은 새 문자부터 다시 비교해야 할 후보입니다. 따라서 기존 배열에 새 위치 하나만 계산해 붙이는 것은 완전한 온라인 Z 갱신이 아닙니다. 후보를 별도로 추적하는 온라인 알고리즘을 설계하거나 안전하게 전체를 다시 계산해야 합니다. 슬라이딩 윈도우처럼 앞쪽 문자를 삭제하면 접두 자체가 바뀌므로 append 전용 추론을 그대로 적용할 수 없습니다.
선택·검증·한계
Z는 한 문자열의 모든 접두 일치 구간을 동시에 얻고, 결합 문자열로 단일 패턴 검색·반복 주기·border 분석을 구성할 때 유용합니다. KMP와 시간 복잡도는 비슷하지만 KMP는 패턴의 border fallback 상태를 직접 유지하고, Z는 각 위치의 접두 일치 길이와 오른쪽 구간을 유지합니다. 여러 패턴을 한 번에 처리하는 목적이면 Aho-Corasick이 더 적합합니다.
검증에는 z[0] 정책, [l,r) 경계, i<r 복사, 복사값의 min 제한, 반복 문자열과 비반복 문자열, 결합 구분자 충돌, append 반례를 포함합니다. aaaabaa의 마지막 위치처럼 z[i-l] > r-i인 상태를 반드시 테스트해야 경계 밖 복사를 잡을 수 있습니다. 여기의 숫자는 설명용 계산이며 실행 결과가 아닙니다.
참고한 cp-algorithms의 “Z-function” 문서는 2026-07-18 갱신본으로, Z 정의, rightmost [l,r) 구간, min(r-i,z[i-l]) 초기화, 선형 시간 증명, p + sep + t 검색과 반복 블록 조건을 설명합니다. 문서는 정적 문자열 입력을 설명하므로 append 온라인 갱신을 일반적으로 보장한다고 해석하면 안 됩니다. 입력 단위, 빈 패턴, separator를 표현할 수 없는 alphabet의 정책은 구현이 정해야 합니다.
참고 경로
위 링크는 개념별 참고 경로이며, 본문에서 명시한 확인 범위와 미확인 구현 조건을 함께 적용합니다.