롤링 해시

문자열의 해시값을 한 글자씩 밀어가며 앞의 해시값으로부터 빠르게 다음 해시값을 계산하는 방법이다. 매번 부분 문자열을 처음부터 다시 해시하지 않고, 맨 앞 글자를 빼고 새 글자를 더하는 식으로 계산하므로 한 글자 이동할 때마다 상수 시간만 든다. 라빈-카프 알고리즘이 이 방식으로 패턴과 같은 길이의 모든 부분 문자열의 해시를 빠르게 비교한다.