긴 텍스트에서 길이 K의 모든 부분 문자열 hash를 한 번씩 갱신할 때 어떤 항을 빼고 더하나요?

왼쪽 문자를 높은 자리로 두는 길이 K 다항식 hash를 c0*p^(K-1)+...+c(K-1)로 정하면, 한 칸 이동할 때 세 단계가 필요합니다. 먼저 오래된 c0의 기여 c0*p^(K-1)를 현재 hash에서 뺍니다. 그러면 남은 c1...c(K-1)이 한 자리씩 왼쪽으로 올라가야 하므로 base p를 곱하고, 마지막에 새 문자 cK를 더합니다. 따라서 next=((current-c0*highPower)*p+cK) mod m, highPower=p^(K-1) mod m입니다. 항을 빼지 않으면 이전 문자가 남고, 이동을 하지 않으면 자릿값이 달라집니다.

p=3, m=101, a=1,b=2,c=3,d=4로 abc→bcd를 추적하면 현재 값은 1*9+2*3+3=18입니다. a의 항 9를 빼 9, 남은 값을 3배 해 27, 새 d=4를 더해 31이 됩니다. 직접 계산한 2*9+3*3+4=31과 일치합니다. 코드에서는 빼기 뒤 음수 residue를 ((x%m)+m)%m처럼 정규화하고, c0*highPower와 곱셈이 고정 폭 정수를 넘지 않는지 확인해야 합니다.

이 식은 K가 고정된 스트리밍 창에 맞습니다. 임의 [l,r)를 자주 묻는 정적 텍스트라면 prefix hash와 power 배열이 더 자연스럽고, hash 일치 뒤 exact equality가 필요한지는 별도 계약입니다. K=0, K>text.length, 빈 텍스트는 window가 정의되지 않으므로 호출자가 오류·빈 결과 중 하나를 명시해야 합니다.

K=1이면 highPower=1이고 next=((current-c0)*p+c1) mod m이 되어 이전 문자를 제거한 뒤 새 문자만 남기는 형태가 됩니다. 반대로 K>text.length이면 첫 window 자체가 없으므로 음수 반복 횟수를 돌지 않게 입력을 거절해야 합니다. 모듈러를 매 단계 적용하면 값의 크기를 줄일 수 있지만, 언어의 곱셈 중간값이 이미 overflow할 수 있으므로 “마지막에만 %m”으로 충분하다고 보면 안 됩니다. 후보 hash 뒤 exact 비교가 필요하면 이 갱신식은 여전히 검색 필터일 뿐입니다.