KMP의 패턴·구분자·텍스트 결합 방식에서 구분자가 입력에 포함되면 무엇이 잘못될 수 있나요?

구분자는 p + sep + t를 한 배열로 만들어 prefix function을 계산할 때만 필요하고, 일반 streaming KMP에는 필요하지 않습니다. 결합식은 sep가 pattern과 text 어느 쪽에도 없다는 전제를 강제해야 합니다. 충돌을 허용한 p=a, sep=#, t=a#a의 결합은 a#a#a입니다. 텍스트의 마지막 a에서 prefix function은 3이 될 수 있어 실제 패턴 길이 m=1보다 커집니다. 그러므로 π==m만 검사하면 그 출현을 놓치며, >=m으로 바꾸더라도 pattern 안에 sep가 없고 text의 경계 토큰이 실제 문자와 구별된다는 조건 없이는 결합 증명이 안전하지 않습니다. 토큰 배열이나 직접 KMP 전이를 선택해야 합니다.

중요한 점은 일반적인 스트리밍 KMP에는 구분자가 필요 없다는 것입니다. 패턴의 π와 현재 상태 j만 가지고 텍스트 문자를 직접 소비하면 경계 충돌 자체가 없습니다. 결합 방식에서 패턴 길이를 m이라 할 때 텍스트의 위치 x는 결합 인덱스 x+m+1에 대응합니다. 그 위치의 π가 m이면 매치이고, 종료 인덱스에서 시작 위치를 계산할 때 m과 구분자 1칸을 빼야 합니다. 이 변환을 빼먹으면 오프바이원이 납니다.

빈 패턴과 구분자를 표현할 수 없는 alphabet은 각각 별도 정책 또는 직접 상태 전이로 처리해야 합니다.

위치를 직접 적어 보면 오프바이원이 줄어듭니다. p=aba, t=ababa에서 결합 문자열은 aba#ababa이고 패턴 길이는 3입니다. 텍스트 위치 0의 a는 결합 인덱스 4에서 시작하고, 패턴이 끝나는 결합 인덱스 6에서 π가 3이 됩니다. 식 6 - 2*3 = 0으로 텍스트 시작을 얻습니다. 텍스트 위치 2의 끝은 결합 인덱스 8이고 8 - 6 = 2입니다. 이처럼 종료 위치와 시작 위치를 분리해 적으면 구분자 칸을 빠뜨렸는지 확인할 수 있습니다.

구분자가 입력에 없는지 런타임에서 검사할 수 있다면 초기화 단계에서 거부하는 편이 낫습니다. 검사하지 않고 특수 문자 하나를 관례로만 정하면 데이터가 추가된 뒤 조용히 결과가 바뀔 수 있습니다. 범용 Unicode 입력에서는 사용자가 입력할 수 없는 sentinel이 없을 수 있으므로, 실제 문자를 하나 더 붙이는 방식보다 토큰 배열 또는 직접 KMP 전이를 택하는 판단이 안전합니다.