Knuth-Morris-Pratt finds every occurrence of a pattern in a text in O(n + m) time. It precomputes a failure function that says, on a mismatch at position j of the pattern, how far to slide the pattern forward without ever re-comparing text characters. Type a text and pattern, then step through the build and search.
For each prefix of length i+1, lps[i] is the length of the longest proper prefix that is also a suffix — the fallback point on a mismatch.
KMP was published in 1977 by Donald Knuth, James H. Morris, and Vaughan Pratt. Its trick is the failure function: while scanning the pattern against the text, whenever the pattern's j-th character mismatches, we already know that the previous j characters of the text matched the pattern's first j. The failure function tells us the longest border of that matched prefix, which is the largest safe self-alignment we can slide the pattern to — without ever re-scanning a character of the text. That gives a strict O(n + m) bound, comparable to Boyer-Moore in the worst case but with far simpler bookkeeping. Modern strstr and grep engines still fall back to KMP-style automata for their exact-match paths.