Page 147 - Data Structures Handout_Neat
P. 147
11.3.4 Rabin-Karp Algorithm
The Rabin-Karp algorithm uses hashing to quickly compare substrings with the target
pattern. It computes a rolling hash for the pattern and for substrings of the text. If the hash
values match, a direct comparison is performed to confirm the result. This approach is
efficient for multiple pattern searches and has an average-case complexity of ( + ).
Example in C++:
147
