Z 배열로 패턴의 모든 출현 위치를 찾을 때 입력을 어떻게 합치고 결과를 해석하나요?

패턴 p와 텍스트 t 사이에 두 입력에 없는 구분자 sep를 넣어 s=p+sep+t를 만든 뒤 Z 배열을 계산합니다. 텍스트의 시작 위치 x에 대응하는 결합 인덱스는 x+|p|+1입니다. 그 위치의 Z 값이 정확히 |p|이면 p가 텍스트 x에서 시작합니다. 예를 들어 p=aba, t=ababa이면 aba#ababa에서 결합 인덱스 4와 6의 Z 값이 3이므로 텍스트 위치 0과 2를 반환합니다.

구분자는 패턴 접두 비교가 텍스트 쪽으로 넘어가도 패턴 자체보다 길어지지 않도록 막습니다. 충돌을 허용하면 z==|p|만 검사하는 코드는 안전하지 않습니다. 예를 들어 p=a, sep=#, t=a#a의 결합은 a#a#a이고 첫 번째 텍스트 a에서 Z가 3까지 늘어날 수 있어, z==1만 검사하면 실제 출현을 놓칩니다. 가장 단순한 계약은 pattern과 text에 모두 없는 토큰을 강제하는 것입니다. 그 계약을 보장할 수 없다면 z>=|p|를 검토하되 pattern 내부의 sep 금지와 토큰 종류 보존을 함께 보장하거나, 아예 직접 streaming KMP를 선택해야 합니다. 결과 위치는 결합 인덱스에서 |p|+1을 빼서 텍스트 offset으로 변환합니다.

이 방식은 전체 결합 문자열과 Z 배열을 저장하므로 시간과 저장은 O(|p|+|t|)입니다. 스트림이 계속되는 경우에는 결합 문자열을 매번 재생성하기보다 KMP 상태를 유지하는 편이 적절할 수 있습니다. 빈 패턴은 모든 위치를 반환할지 별도 정책을 정해야 합니다.

패턴 검색에서 z가 패턴보다 길어지는 것을 걱정할 필요는 구분자가 올바를 때 줄어듭니다. 패턴과 텍스트 사이의 sentinel을 만나면 결합 문자열의 접두와 같은 문자를 계속 이어갈 수 없으므로, 텍스트 위치에서 z가 |p|이면 정확히 패턴 전체가 일치했다는 뜻입니다. sentinel이 텍스트에 들어 있으면 이 논리가 보장되지 않아, == 판정으로 실제 출현을 놓칠 수 있고 토큰 경계 해석도 구현 계약과 달라집니다.

빈 텍스트는 결합 문자열에 패턴과 sentinel만 남고 결과가 없습니다. 패턴이 텍스트보다 길어도 z가 패턴 길이에 도달하지 않으므로 매치가 없습니다. 이런 경계 입력을 먼저 정의하면 위치 순회 범위도 0..|t|-1로 고정할 수 있습니다. 출력은 겹치는 매치도 모두 포함해야 하므로 p=aa, t=aaa에서 0과 1을 모두 반환하는 테스트가 필요합니다.