Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt algorithm is a string searching algorithm that uses a prefix table to skip over characters that are known to not match the pattern.

Algorithm

1. Construct the prefix table for the pattern.
2. Use the prefix table to skip over characters that are known to not match the pattern.
3. If the pattern is found, return the index of the pattern in the text.
4. If the pattern is not found, return -1.