Hash 후 덧셈, 뺄셈을 통해 그 다음 해시를 계산 할 수 있는 개념 롤링 해시를 사용하면 이전 해시 값과 O(1) 시간 복잡도로 새로운 해시 값을 계산할 수 있습니다.
예를 들어, 서브스트링 s[1..k]의 해시 값이 H라고 하면, s[2..k+1]의 해시 값을 H를 이용해 빠르게 계산할 수 있습니다. 이 때 주로 다음과 같은 방식으로 해시 값을 업데이트합니다.
New Hash=Roll(Old Hash−oldest element×base(length−1))×base+newest elementNew Hash=Roll(Old Hash−oldest element×base(length−1))×base+newest element
이렇게 하면 각 이동마다 상수 시간에 해시 값을 계산할 수 있으므로, 전체 시간 복잡도는 O(N)이 됩니다 (N은 텍스트의 길이).