Edit page

Knuth Morris Pratt

Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (Source: Wikipedia)

Complexity

NamePreprocessingAverageWorstSpaceComments
Knuth Morris Prattmn + mn + mm

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

References

  • Geeksforgeeks
  • Wikipedia
  • YouTube