In computer science, the Rabin – Karp algorithm or Karp – Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987)In contrast, the Aho – Corasick algorithm can find all matches of multiple shapes in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches).
# Numbers of alphabet which we call base alphabet_size = 256 # Modulus to hash a string modulus = 1000003 def rabin_karp(pattern, text): """ The Rabin-Karp Algorithm for finding a pattern within a piece of text with complexity O(nm), most efficient when it is used with multiple patterns as it is able to check if any of a set of patterns match a section of text in o(1) given the precomputed hashes. This will be the simple version which only assumes one pattern is being searched for but it's not hard to modify 1) Calculate pattern hash 2) Step through the text one character at a time passing a window with the same length as the pattern calculating the hash of the text within the window compare it with the hash of the pattern. Only testing equality if the hashes match """ p_len = len(pattern) t_len = len(text) if p_len > t_len: return False p_hash = 0 text_hash = 0 modulus_power = 1 # Calculating the hash of pattern and substring of text for i in range(p_len): p_hash = (ord(pattern[i]) + p_hash * alphabet_size) % modulus text_hash = (ord(text[i]) + text_hash * alphabet_size) % modulus if i == p_len - 1: continue modulus_power = (modulus_power * alphabet_size) % modulus for i in range(0, t_len - p_len + 1): if text_hash == p_hash and text[i : i + p_len] == pattern: return True if i == t_len - p_len: continue # Calculate the https://en.wikipedia.org/wiki/Rolling_hash text_hash = ( (text_hash - ord(text[i]) * modulus_power) * alphabet_size + ord(text[i + p_len]) ) % modulus return False def test_rabin_karp(): """ >>> test_rabin_karp() Success. """ # Test 1) pattern = "abc1abc12" text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc" text2 = "alskfjaldsk23adsfabcabc" assert rabin_karp(pattern, text1) and not rabin_karp(pattern, text2) # Test 2) pattern = "ABABX" text = "ABABZABABYABABX" assert rabin_karp(pattern, text) # Test 3) pattern = "AAAB" text = "ABAAAAAB" assert rabin_karp(pattern, text) # Test 4) pattern = "abcdabcy" text = "abcxabcdabxabcdabcdabcy" assert rabin_karp(pattern, text) # Test 5) pattern = "Lü" text = "Lüsai" assert rabin_karp(pattern, text) pattern = "Lue" assert not rabin_karp(pattern, text) print("Success.") if __name__ == "__main__": test_rabin_karp()