Rabin Karp 알고리즘이 패턴 문자열에 대해 2 개의 해시 함수를 필요로하는 이유는 무엇입니까?

Question

예를 들어, string1 : "AB"가 string2 : "CABA"에 있어야합니다.string1 h1 = ('A'* 27 + 'B') 및 h2 = ('A'* 29 + 'B')에 대해 string2에 대해 hash1 및 hash2 함수를 계산합니다 (h2.1 = 'C'* 27 + 'A', h2.2 = 'C'* 29 + 'C') 결과를 string1의 해시 함수와 비교합니다.

모든 문자열 또는 하위 문자열에 대해 서로 다른 두 개의 해시 함수가 필요한 이유를 이해할 수 없습니다.

Answer 1

두 개의 서로 다른 해시 함수를 사용하면 충돌 가능성이 줄어들지 만 한 해시 함수가있는 버전도 작동합니다 (두 번째 함수가 항상 필요한 것은 아닙니다).