Michael O. Rabin과 Richard M. Karp가 함께 만든 이 알고리즘은 문자열 검색을 위해 해쉬값 함수를 이용한다. 매번 문자 하나씩 비교하지 않고 패턴의 해쉬와 부분 문자열의 해쉬만을 비교하기 때문에 상당히 빠른 성능을 보여주고 구현도 쉬운 편이다. 해쉬값의 생성 해쉬값은 문자들에 어떤 가공을 해서 일정한 패턴으로 만들어내는 값으로 문자열이 가지고 있는 hashCode와는 다른 값이다. 패턴의 해쉬값은 당연히 고정되어있다. 비교 대상인 문자열의 해쉬값은 패턴 불일치로 대상 범위가 달라질 때마다 매번 계산되어야 한다. 이때 계산되는 해쉬는 아주 빠른 시간에 처리되어야 하고 새로 들어오는 문자와 나가는 문자의 처리에서 일관성이 있어야 한다. 이를 위해 패턴은 통상 아래 수식으로 계산된다. ..