cgiosy.dev

어떤 집합에서 결합법칙을 만족하는 이항연산 $+$와 역연산 $-$가 있고, $f(x + y) = f(x) + f(y)$를 만족하는 함수 $f$가 있을 때, $f^n(x)$를 빠르게 계산할 수 있다면 길이 $N$의 문자열 $S$에 대해 $h = \sum_{k=1}^{N}{f^{N-k}(S[k])}$를 롤링 해시로 활용할 수 있다. $f(h) + S[N + 1]$로 뒤에 문자를 추가할 수 있고, $h - f^{N-1}(S[1])$로 앞에서 문자를 삭제할 수 있다. 당연히 중간에서 삭제 및 대체도 가능하지만, 앞뒤 추가 및 삭제에 비해 거의 안 쓰이는 편이다. 예시 위키피디아의 롤링 해시 문서에선 다음 두 가지 다항식 기반 롤링 해시를 소개한다. 다항식 롤링 해시 적당한 상수 $p$, $q$가 있을 때, mo..