strings.rabin_karp¶

Attributes¶

`alphabet_size`
`modulus`

Functions¶

`rabin_karp`(→ bool)	The Rabin-Karp Algorithm for finding a pattern within a piece of text
`test_rabin_karp`(→ None)

Module Contents¶

strings.rabin_karp.rabin_karp(pattern: str, text: str) → bool¶

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

Calculate pattern hash
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

strings.rabin_karp.test_rabin_karp() → None¶

>>> test_rabin_karp()
Success.

strings.rabin_karp.alphabet_size = 256¶

strings.rabin_karp.modulus = 1000003¶