KMP Algorithm is one of the most popular pattern matching algorithms. KMP stands for Knuth Morris Pratt. KMP algorithm was invented by Donald Knuth and Vaughan Pratt together and independently by James H Morris in the year 1970. In the year 1977,all the three jointly published KMP Algorithm.
KMP algorithm was the first linear time complexity algorithm for string matching.
KMP algorithm is one of the string matching algorithms used to find a Pattern in a Text.
KMP algorithm is used to find a "Pattern" in a "Text". This algorithm campares character by character from left to right. But whenever a mismatch occures it uses a preprocessed table called "Prefix Table" which is used to skip characters comparison while matching. Some times prefix table is also known as LPS Table. Here LPS stands for "Longest proper Prefix which is also Suffix".
Steps for Creating LPS Table (Prefix Table)
- Step 1 - Define an one dimensional array with the size equal to the length of the Pattern. (LPS[size])
- Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS = 0.
- Step 3 - Compare the characters at Pattern[i] and Pattern[j].
- Step 4 - If both are matching then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.
- Step 5 - If both are not matching then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and increment 'j' value by one, if it is none '0' then set i = LPS[i-1]. Goto Step 3.
- Step 6- Repeat the above steps until all the value of LPS are filled.
Let us see the above steps to create prefix table for a pattern...
How to use LPS Table
We use the LPS table to decide that from which character we need to start comparing when a mismatch occured.
When a mismatch occures, consider the LPS value of previous character to the mismatched character inthe pattern. If it is '0' then start comparing first character of the pattern with next character to the mismatched character in text. If it is not '0' then start the character which is at index value equal to the LPS value of previous character to the mismatched character in pattern with the mismatched character in Text.
How the KMP Algorithm Works
Let us see a working example of KMP Algorithm to find a Pattern in a Text...