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 simp
(pattern, text)
| 1 | def rabin_karp(pattern, text): |
| 2 | """ |
| 3 | |
| 4 | The Rabin-Karp Algorithm for finding a pattern within a piece of text |
| 5 | with complexity O(nm), most efficient when it is used with multiple patterns |
| 6 | 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. |
| 7 | |
| 8 | This will be the simple version which only assumes one pattern is being searched for but it's not hard to modify |
| 9 | |
| 10 | 1) Calculate pattern hash |
| 11 | |
| 12 | 2) Step through the text one character at a time passing a window with the same length as the pattern |
| 13 | calculating the hash of the text within the window compare it with the hash of the pattern. Only testing |
| 14 | equality if the hashes match |
| 15 | |
| 16 | """ |
| 17 | p_len = len(pattern) |
| 18 | p_hash = hash(pattern) |
| 19 | |
| 20 | for i in range(0, len(text) - (p_len - 1)): |
| 21 | |
| 22 | # written like this t |
| 23 | text_hash = hash(text[i:i + p_len]) |
| 24 | if text_hash == p_hash and \ |
| 25 | text[i:i + p_len] == pattern: |
| 26 | return True |
| 27 | return False |
| 28 | |
| 29 | |
| 30 | if __name__ == '__main__': |