From Wikipedia: 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. Knuth Morris Pratt search runs in linear time in the length of W and S.
Properties
- Case performance O(s + w)
- Case space complexity O(w)
From Wikipedia: find a longest palindrome in a string in linear time.
Properties
- Worst-case time complexity is O(n)
- Worst-case space complexity is O(n)
From Wikipedia: a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text.