1 month, 2 weeks

Knuth–Morris–Pratt Algorithm for Pattern Searching




Knuth Morris Pratt (KMP) is an algorithm, which checks the characters from left to right. However, at whatever point a mismatch happens, it utilizes a preprocessed table called "Prefix Table" to skip characters examination while matching. A few times prefix table is otherwise called LPS Table. This algorithm was conceived by Donald Knuth and Vaughan Pratt and independently by James H.Morris in 1977.
The naive string matching algorithm would either use a sliding window or a two-pointer approach which would result in extra comparisons. The time complexity for the naive algorithm would be O(mn).

Components of the KMP algorithm:
a. Prefix.                                                                                                               
b. Suffix.                                                                                                               
c. LPS table : Table for detecting the Longest Proper Prefix that is also a Suffix

How do the iterators move?

-If there is a match, increment both i and j.
-If there is a mismatch after a match, place j at LPS[pattern[j - 1]] and compare again.
-If j = 0, and there is a mismatch, increment i.


lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i]. 

txt[] = "AAAAABAAABA"                                                                                 
pat[] = "AAAB"                                                                                                 
lps[] = {0, 1, 2, 0}                                                                                             

i = 0, j = 0                                                                                                        
txt[] = "AAAAABAAABA"                                                                                 
pat[] = "AAAB"                                                                                                
txt[i] and pat[j] match, do i++, j++                                                                  

i = 1, j = 1                                                                                                     
txt[] = "AAAAABAAABA"                                                                              
pat[] = "AAAB"                                                                                              
txt[i] and pat[j] match, do i++, j++                                                                 

i = 2, j = 2                                                                                                      
txt[] = "AAAAABAAABA"                                                                               
pat[] = "AAAB"                                                                                              
pat[i] and pat[j] match, do i++, j++                                                                 

i = 3, j = 3                                                                                                      
txt[] = "AAAAABAAABA"                                                                               
pat[] = "AAAB"                                                                                               
txt[i] and pat[j]  do not match, do i++, j = lps[j - 1]                                         

def KMPSearch(pat, txt):                                                                              
       M = len(pat)                                                                                           
       N = len(txt)                                                                                            
       lps = [0]*M                                                                                            
       j = 0                                                                                                      
       i = 0                                                                                                      

      computeLPSArray(pat, M, lps)                                                             
      while (N - i) >= (M - j):                                                                          
            if pat[j] == txt[i]:                                                                              
                i += 1                                                                                          
                j += 1                                                                                          
           if j == M:                                                                                           
               print ("Found pattern at index " + str(i-j))                                      
               j = lps[j-1]                                                                                       
 
        # mismatch after j matches                                                                   
          elif i < N and pat[j] != txt[i]:                                                                 
               if j != 0:                                                                                           
                   j = lps[j-1]                                                                                   
               else:                                                                                              
                  i += 1                                                                                           
 
def computeLPSArray(pat, M, lps):                                                             
      len = 0    # length of the previous longest prefix suffix                           
      i = 1                                                                                                        
      while i < M:                                                                                            
          if pat[i]== pat[len]:                                                                              
              len += 1                                                                                          
              lps[i] = len                                                                                      
              i += 1                                                                                             
          else:                                                                                                  
              if len != 0:                                                                                      
                  len = lps[len-1]                                                                          
              else:                                                                                              
                  lps[i] = 0                                                                                     
                  i += 1                                                                                          

In this algorithm, we have 2 pointers and we work on the LPS table and the string. We compare string[i] and pattern[j]. There are 3 operations that could happen on an iteration of the while loop:

a. String match, increment i and j                                                                                         

b. String mismatch, but j > 0, so move j to LPS[j - 1] and leave i as it is and compare         

c. String mismatch, but j = 0, so increment i and compare.                                                   

O(m) - It is to compute the prefix function values. O(n) - It is to compare the pattern to the text.
Time complexity of the complete algorithm is O(m + n).

Advantages of the KMP algorithm
-A very obvious advantage of the KMP algorithm is it's time complexity. It's very fast as compared to any other exact string matching algorithm.
-The running time of the KMP algorithm is optimal (O(m + n)), which is very fast.
-The algorithm never needs to move backwards in the input text T. It makes the algorithm good for processing very large files.

Disadvantage of the KMP algorithm
The only disadvantage of the KMP algorithm is that it is very complex to understand.

It's uses are :
-Checking for Plagiarism in documents etc
-Bioinformatics and DNA sequencing
-DNA pattern matching algorithms
-Digital Forensics
-Spelling checkers
-Spam filters
-Search engines, or for searching content in large databases
-Intrusion detection system

 


Responses(0)