Rabin-Karp Algorithm for Pattern Searching
Rolling hash:
Step-by-Step Animation
Animation Speed
Elaboration:
?
Rabin-Karp: It uses a rolling hash to filter out substrings that do not match the pattern.A rolling hash is able to calculate the new hash value from the old hash value, the new added value at the end, the removed value in the beginning quickly.
Moving sum rolling hash: The hash function is:
H(S[i, j]) = (S[i] + S[i + 1] + S[i + 2] ··· S[j]) % m
The above equation can also be written as:
H(S[i, j]) = (···( ( ( S[i] % m ) + S[i + 1] ) % m + S[i+2] ) % m ··· + S[j]) % m
Therefore, we can calculate the hash value iteratively to avoid integer overflow:
H = 0
for index from i->j(inclusive):
H = (H + S[index]) % m;
The new hash value can be calculated using the following formular:
H(S[i, j]) = ( H(S[i - 1, j - 1]) - S[i - 1] + S[j] ) % m
Polynomial rolling hash(Rabin fingerprint): The hash function is (b and m are contant, and L = j - i):
H(S[i, j]) = ( S[i] · bL - 1 + S[i + 1] · bL - 2 + · · · + S[i + L - 1]) · b1 + S[i + L] · b0) % m
The above equation can also be written as:
H(S[i, j]) = (b·(···( b · ( b · ( S[i] % m ) + S[i+1] ) % m + S[i+2] ) % m + ··· ) % m + S[j]) % m
Therefore, we can calculate the hash value iteratively:
H = 0
for index from i->j(inclusive):
H = (b * H + S[index]) % m;
The new hash value can be calculated using the following formular:
H(S[i, j]) = ( b · ( H(S[i - 1, j - 1]) – bL - 2 · S[i - 1] ) + S[j] ) ) % m