algorithm
नूथ मॉरिस प्रैट (केएमपी) एल्गोरिथम

परिचय

KMP-उदाहरण

कलन विधि

यह एल्गोरिथ्म एक दो कदम प्रक्रिया है। पहले हम एक सहायक सरणी lps [] बनाते हैं और फिर पैटर्न को खोजने के लिए इस सरणी का उपयोग करते हैं।

प्रीप्रोसेसिंग :

1. हम पैटर्न को पूर्व-संसाधित करते हैं और सहायक सरणी lps बनाते हैं [] जिसका उपयोग मिलान करते समय वर्णों को छोड़ने के लिए किया जाता है।
2. यहाँ lps [] सबसे लंबे समय तक उचित उपसर्ग को इंगित करता है जो प्रत्यय भी है। उचित उपसर्ग उपसर्ग है जिसमें संपूर्ण स्ट्रिंग शामिल नहीं है। उदाहरण के लिए, स्ट्रिंग ABC के उपसर्ग "" , "ए" , "एबी" और "एबीसी" हैं । उचित उपसर्ग "" , "ए" और "एबी" हैं । स्ट्रिंग के प्रत्यय "" , "C" , "BC" और "ABC" हैं ।

खोज कर

1. हम मिलान वाले वर्णों को [i] और पैट [j] रखते हैं और [j] और txt [i] के मिलान के दौरान i और j को बढ़ाते रहते हैं।

2. जब हम एक बेमेल देखते हैं, तो हम जानते हैं कि अक्षर [0..j-1] txt [i-j + 1… i-1] से मेल खाते हैं। हम यह भी जानते हैं कि lps [j-1] पैट के वर्णों की गिनती है। [०… j-१] जो कि दोनों उचित उपसर्ग और प्रत्यय हैं। इससे हम यह निष्कर्ष निकाल सकते हैं कि हमें इन lps [j-१] वर्णों के txt [ij… i-१] से मेल खाने की आवश्यकता नहीं है क्योंकि हम जानते हैं कि ये वर्ण हैं वैसे भी मैच होगा।

जावा में कार्यान्वयन

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;
    }

}