The Knuth–Morris–Pratt string searching algorithm (or
KMP algorithm) searches for occurrences of a “word” W
within a main “text string” T 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.
O(|W| + |T|) (much faster comparing to trivial O(|W| * |T|))O(|W|)