Horje

KMP example - Knuth Morris Pratt (KMP) Algorithm - Algorithm
Learn
Algorithm - Knuth Morris Pratt (KMP) Algorithm - Kmp example
KMP-Example

Algorithm

This algorithm is a two step process.First we create a auxiliary array lps[] and then use this array for searching the pattern.

Preprocessing :

  • We pre-process the pattern and create an auxiliary array lps[] which is used to skip characters while matching.
  • Here lps[] indicates longest proper prefix which is also suffix.A proper prefix is prefix in which whole string is not included.For example, prefixes of string **ABC** are **“ ”**, **“A”**, **“AB”** and **“ABC”**. Proper prefixes are **“ ”**, **“A”** and **“AB”**. Suffixes of the string are **“ ”**, **“C”**, **“BC”** and **“ABC”**.

    • Searching

  • We keep matching characters **txt[i]** and **pat[j]** and keep incrementing i and j while **pat[j]** and **txt[i]** keep matching.
  • When we see a mismatch,we know that characters **pat[0..j-1]** match with **txt[i-j+1…i-1]**.We also know that lps[j-1] is count of characters of **pat[0…j-1]** that are both proper prefix and suffix.From this 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.

    • Implementaion in Java

    public class KMP {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str = "abcabdabc";
        String pattern = "abc";
        KMP obj = new KMP();
        System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
    }
    
    public int[] computeLPS(char[] str){
        int lps[] = new int[str.length];
        
        lps[0] = 0;
        int j = 0;
        for(int i =1;i<str.length;i++){
            if(str[j] == str[i]){
                lps[i] = j+1;
                j++;
                i++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    lps[i] = j+1;
                    i++;
                }
            }
            
        }
        
        return lps;
    }
    
    public boolean patternExistKMP(char[] text,char[] pat){
        int[] lps = computeLPS(pat);
        int i=0,j=0;
        while(i<text.length && j<pat.length){
            if(text[i] == pat[j]){
                i++;
                j++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    i++;
                }
            }
        }
        
        if(j==pat.length)
            return true;
        return false;
    }

}


    Read Article
    https://develop.horje.com/learn/1434/reference

     

    Horje