Rabin-Karp에서 해시가 같은 두 윈도우를 발견했을 때 바로 match로 반환하면 안 되는 이유는 무엇인가요?

rolling hash는 길이 K인 원문을 하나의 유한한 숫자로 압축하므로 서로 다른 윈도우도 같은 값을 낼 수 있습니다. 따라서 패턴 hash와 텍스트 윈도우 hash가 같다는 것은 값싼 후보 판정이지 문자열 동일성의 증명이 아닙니다. 예를 들어 선택한 modulus에서 hash(ab)=hash(ba)가 될 수 있는데, 패턴이 ab이고 텍스트의 현재 윈도우가 ba라면 hash만 보고 즉시 match를 반환하는 구현은 거짓 양성을 냅니다. 정확한 검색은 후보 위치에서 K개의 문자 또는 canonical bytes를 다시 비교해 충돌을 제거합니다.

후보 생성은 prefix hash로 [i,i+K)를 계산하거나 fixed-window 식으로 갱신합니다. 이 산술은 긴 텍스트를 매 위치에서 처음부터 읽지 않게 해 주지만, 마지막 equality 검사를 없애지는 않습니다. 비적대적 입력에서는 실제 후보 수가 적어 재비교 비용이 작을 수 있지만, 특정 modulus를 노린 입력이나 반복 문자열에서는 후보가 많아져 최악에 가까운 O((n-K+1)K) 검증 비용이 발생할 수 있습니다. 결과가 보안 승인이나 무결성 판정이면 일반 rolling hash를 단독 증거로 사용하지 않고, 결정적 비교 또는 MAC·서명 같은 별도 구조를 둡니다.

double hash는 두 fingerprint가 모두 같은 창만 후보로 만들어 우연한 충돌을 줄일 수 있지만, 원문 비교를 요구하지 않는다는 의미는 아닙니다. 확률적 오탐을 허용하는 필터인지 exact 검색인지 먼저 계약하고, 빈 패턴·K>n·정규화된 입력의 비교 단위를 테스트해야 합니다.

검증 루프는 hash가 같은 위치에서 text[i:i+K]와 pattern을 직접 비교한 뒤에만 결과 목록에 넣어야 합니다. hash가 다른 위치는 즉시 버릴 수 있지만, hash가 같은 위치를 곧바로 승인하면 필터가 판정기가 됩니다. K=1에서는 후보 검증이 한 문자지만, K가 길고 반복 텍스트인 경우 같은 접두를 여러 번 읽을 수 있습니다. 이 비용을 줄이려면 정확한 단일 패턴 검색에는 KMP, 고정 텍스트 다중 질의에는 suffix array 같은 구조가 더 예측 가능한 선택입니다.