길이가 같은 구간 비교
패턴 길이가 m이면 본문에서 길이 m인 구간들을 차례로 살핀다. 각 구간과 패턴의 해시가 다르면 그 구간은 일치하지 않는다. 해시가 같으면 일치 후보로 남긴다. 패턴이 본문보다 길면 검사할 구간이 없으며, 빈 패턴은 별도의 검색 규칙을 정해야 한다.
한 칸 이동하는 해시
본문 구간이 한 칸 오른쪽으로 이동하면 맨 앞 문자가 빠지고 새 문자가 뒤에 들어온다. 롤링 해시는 이 변화를 반영해 전체 구간을 다시 읽지 않고 해시를 갱신한다. 접두 해시를 미리 계산해 각 구간의 값을 얻는 구현도 가능하다.
후보와 실제 일치
예를 들어 본문이 cabcab이고 패턴이 cab이면 시작 위치 0과 3이 실제 일치다. 해시가 같은 다른 구간이 있더라도 문자가 다르면 거짓 후보다. 해시의 동일성만으로 결과를 확정하는 방식과, 원문 비교로 모든 후보를 검증하는 방식은 정확성 보장이 다르다.
최악의 경우와 검증 비용
해시 계산과 구간 순회만 보면 본문 길이 n과 패턴 길이 m에 대해 O(n+m)으로 처리할 수 있다. 하지만 후보마다 최대 m개의 문자를 확인한다면 많은 충돌이나 실제 일치가 있을 때 총시간이 O(nm)까지 커질 수 있다. 빠른 기대 성능을 모든 입력에 대한 최악 시간 보장으로 설명해서는 안 된다.