C++ Program for KMP Algorithm | Advanced String Searching | Knuth-Morris-Pratt Algorithm | Pattern Matching

Let's say we are given a string 'txt' and a pattern 'pat' and we have to find out the number of times the pattern is found in the string.

KMP Algorithm Key Idea :

The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to linear time.

The basic idea behind KMP’s algorithm is that whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window and so we take advantage of this information to avoid matching the characters that we know will match anyway.

Implementation Approach :

The algorithm preprocesses the 'pat' string and constructs a lps array of size m (same as size of pattern) which is used to skip characters while matching. The name lps indicates longest proper prefix which is also suffix.

Now for the actual searching part:

i) We know that characters pat [0..j-1] match with txt [i-j…i-1] ( Note that j starts with 0 and increment it only when there is a match )

ii) We also know (from above definition) that lps [j-1] is count of characters of pat[0…j-1] that are both proper prefix and suffix.

From above two points, we can conclude that we do not need to match these lps [j-1] characters with txt [i-j…i-1] because we know that these characters will match anyway.

Program Code :

Sample Output 1 :

Sample Output 2 :