Rabin Karp
Is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern. (Source: Wikipedia)
Complexity​
| Name | Preprocessing | Average | Worst | Space | Comments |
|---|---|---|---|---|---|
| Rabin Karp | m | n + m | n * m | m |
* Where n = length of the source; m = length of the query pattern; k = size of the Alphabet