algorithm => Algoritme van Knuth Morris Pratt (KMP)

Invoering

De KMP is een patroonvergelijkingsalgoritme dat zoekt naar het voorkomen van een "woord" W binnen een hoofd "tekststring" S door de observatie te gebruiken dat wanneer er een mismatch optreedt, we voldoende informatie hebben om te bepalen waar de volgende match kan beginnen. gebruik maken van deze informatie om te voorkomen dat het afstemmen van de personages die we kennen zullen toch match.The worst case complexiteit voor het zoeken van een patroon gereduceerd tot O (n).

KMP-Voorbeeld

Algoritme

Dit algoritme is een proces in twee stappen. Eerst maken we een hulparray lps [] en gebruiken deze array vervolgens om het patroon te doorzoeken.

Voorbewerking :

We verwerken het patroon vooraf en maken een hulparray lps [] die wordt gebruikt om tekens over te slaan tijdens het matchen.
Hier geeft lps [] het langste juiste voorvoegsel aan, dat ook een achtervoegsel is. Een geschikt voorvoegsel is een voorvoegsel waarin de hele tekenreeks niet is opgenomen. Voorvoegsels van tekenreeks ABC zijn bijvoorbeeld "" , "A" , "AB" en "ABC" . Juiste voorvoegsels zijn "" , "A" en "AB" . Achtervoegsels van de tekenreeks zijn "" , "C" , "BC" en "ABC" .

Zoeken

We blijven de tekens txt [i] en pat [j] matchen en blijven i en j ophogen terwijl pat [j] en txt [i] blijven matchen.
Wanneer we een mismatch zien, weten we dat tekens pat [0..j-1] overeenkomen met txt [i-j + 1 ... i-1] . We weten ook dat lps [j-1] het aantal tekens van pat is [0 ... j-1] die zowel het juiste voorvoegsel als het achtervoegsel zijn. Hieruit kunnen we concluderen dat we deze lps [j-1] tekens niet hoeven te matchen met txt [ij ... i-1] omdat we weten dat deze tekens komt toch overeen.

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

}

Modified text is an extract of the original Stack Overflow Documentation

Licentie onder CC BY-SA 3.0

Niet aangesloten bij Stack Overflow

algorithm
Algoritme van Knuth Morris Pratt (KMP)

Zoeken…

Invoering

KMP-Voorbeeld