Knuth-Morris-Pratt Algorithm
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.
Complexity
- Time:
O(|W| + |T|)(much faster comparing to trivialO(|W| * |T|)) - Space:
O(|W|)