KMP (Knuth-Morris-Pratt) Algorithm

algorithm
string-algorithm
pattern-searching
knuth-morris-pratt-kmp

(Team) #1

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/