Z 배열을 만든 문자열 뒤에 문자를 붙였습니다. 기존 Z값 중 끝에 닿던 항목이 바뀔 수 있는 이유는 무엇인가요?

문자열 끝에 문자를 붙이면 기존 문자열에서 끝까지 일치해 더 비교할 수 없었던 suffix-prefix 비교가 새 문자까지 연장될 수 있습니다. 그래서 정적 Z 배열의 값 하나를 새 위치에 추가하는 것만으로는 충분하지 않습니다. 가장 작은 예가 aaa입니다. 기존 Z는 [0,2,1]이고 옛 길이는 3입니다. 위치 1은 1+2=3, 위치 2는 2+1=3으로 둘 다 옛 끝에 닿습니다. 마지막에 a를 붙여 aaaa가 되면 위치 1은 2→3, 위치 2는 1→2로 함께 늘어납니다. 새 문자가 같은 a라서 각 경계 후보에서 한 칸 더 확인됐기 때문입니다.

반대로 기존 값이 옛 끝에 닿지 않았다면 append가 그 비교 범위 밖의 문자를 바꾸지 않으므로 그대로일 수 있습니다. 하지만 어떤 항목들이 옛 경계에 닿았는지와 그 연장 결과를 관리하는 별도 알고리즘 없이는 전체 배열을 안전하게 갱신했다고 할 수 없습니다. 참조되는 일반 Z 알고리즘은 고정된 전체 문자열을 왼쪽에서 오른쪽으로 계산하는 정적 알고리즘입니다.

따라서 온라인 입력에는 전체 재계산, append 전용 자료구조, 또는 패턴 검색만 필요하다면 KMP의 현재 상태를 선택합니다. 앞쪽 문자를 삭제하는 sliding window는 접두 자체가 바뀌므로 append 반례와 같은 방식으로 처리할 수 없습니다.

이 문제를 정적 알고리즘의 상태로 설명하면, 기존 r은 옛 문자열 끝을 넘지 않는다는 조건으로만 유효합니다. append 뒤에는 새 r이 생기고, 과거의 어떤 z[i]가 i+z[i]=oldLength였는지 찾아 연장을 시도해야 합니다. 여러 위치가 동시에 옛 끝에 닿을 수 있으므로 새 문자 하나를 보고 한 위치만 고치면 다른 값이 빠질 수 있습니다. 그래서 온라인 버전은 정적 함수의 마지막 반복을 재사용하는 정도가 아니라, 연장 후보를 관리하는 별도 설계입니다.

aaa의 두 후보는 모두 옛 끝에 닿았습니다. 위치 1은 접두 aa와 suffix aa가 끝에서 끝났고, 위치 2도 한 글자 a가 옛 마지막 위치에서 끝났습니다. 네 번째 a가 들어오면 비교 구간은 각각 aaa와 aa로 길어져 z[1]=3, z[2]=2가 됩니다. 따라서 i+z[i] < oldLength인 값만 새 문자로는 연장되지 않는다고 기록해야 하며, ==인 모든 항목을 후보로 관리해야 합니다. 이 차이를 표로 기록하면 append가 “새 마지막 z만 추가”가 아니라 기존 경계에 닿은 값의 수정 문제라는 점이 드러납니다.