Edit page

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

NamePreprocessingAverageWorstSpaceComments
Rabin Karpmn + mn * mm

* Where n = length of the source; m = length of the query pattern; k = size of the Alphabet

References

  • Geeksforgeeks
  • Wikipedia
  • YouTube