Z 알고리즘이 현재 위치의 비교를 이미 계산한 [l,r) 구간에서 시작할 수 있는 이유는 무엇인가요?

현재 위치 i가 가장 오른쪽 일치 구간 [l,r) 안, 즉 i<r에 있다면 s[l..r)는 s[0..r-l)와 이미 일치한다고 알고 있습니다. 따라서 현재 위치의 접두 비교는 접두 기준 대응 위치 i-l의 Z 값에서 시작할 수 있습니다. 다만 z[i-l] 전체를 그대로 믿으면 오른쪽 경계 r 밖까지 확장할 수 있으므로 초기값은 min(z[i-l], r-i)입니다. r-i는 현재 구간 안에서 확실히 아는 남은 길이입니다.

예를 들어 i=6, 기존 구간이 [5,7)이면 대응 위치는 1이고 z[1]=3일 수 있습니다. 하지만 현재 위치에서 확정된 문자는 r-i=1개뿐이므로 초기값은 min(3,1)=1입니다. 그 뒤 비교는 s[7]부터 실제로 수행합니다. 이 경계 밖 비교가 일치하면 r이 앞으로 이동하고, 아니면 1에서 멈춥니다.

구간을 [l,r]로 해석하거나 i-l을 l-i로 계산하면 복사값이 잘못됩니다. Z 알고리즘의 선형성도 이 경계 재사용에 기대므로, 단순히 “이전 값 복사”라고 설명하면 중요한 안전 조건을 빠뜨린 것입니다.

선형성 설명도 이 상태와 연결됩니다. 내부 위치에서 z[i-l] < r-i이면 이미 알고 있는 구간 안에서 값이 끝나므로 추가 비교가 필요하지 않습니다. z[i-l] >= r-i여서 제한한 초기값이 r-i일 때만 경계 r 바깥의 문자를 비교하고, 성공한 각 비교가 r을 오른쪽으로 늘립니다. 따라서 nested while가 있더라도 성공 비교의 총수는 문자열 길이를 넘지 않습니다. 이 불변식을 코드 리뷰에서 직접 확인하면 “while가 있으니 O(n²)”라는 오해와 “무조건 이전 값을 복사하면 된다”는 오류를 동시에 잡을 수 있습니다.

인덱스 구현에서는 i-l이 항상 현재 구간 안의 대응 좌표인지, z[i]가 초기화된 뒤 while가 그 위치부터 비교하는지를 확인합니다. 빈 구간에서 i<r 분기가 실행되지 않아야 하며, i+z[i]가 문자열 길이를 넘지 않도록 종료 조건을 먼저 둡니다. 이 세 경계가 어긋나면 반복 문자 입력에서만 오류가 나 재현이 늦어집니다.