Knuth-Morris-Pratt String Search algorithm searches for a string (also called pattern) within larger string.
It pre-computes a lookup table using the pattern.
Lookup table helps in avoiding check for characters matches at each index of string.
If characters do not match at any index, it uses the lookup table to shift the pattern where there is a possibility of match.
It has worst case complexity of O(m + n). Where m is length of pattern and n is length of string.