KMP algorithm is a perfect example of how a mismatch can help find a match faster. This improved the time complexity from O(NM) to O(N+M)

**Knuth Morris Pratt pattern searching algorithm** searches for occurrences of a pattern P within a string S using the key idea that when a mismatch occurs, the pattern P has sufficient information to determine where the next potential match could begin thereby avoiding several unnecessary matching bringing the time complexity to linear.

**Read this article to understand the intuition behind KMP algorithm**

The algorithm was developed in 1970 by Donald Knuth and Vaughan Pratt.

**Have a doubt or thought? Join the discussion now**

This is a companion discussion topic for the original entry at http://iq.opengenus.org/knuth-morris-pratt-algorithm/