algorithm => Algorithme Knuth Morris Pratt (KMP)

Introduction

Le KMP est un algorithme de recherche de modèle qui recherche les occurrences d'un "mot" W dans une "chaîne de texte" S principale en utilisant l'observation que, en cas d'incompatibilité, nous disposons des informations suffisantes pour déterminer où la prochaine correspondance pourrait commencer. tirer parti de cette information pour éviter de faire correspondre les caractères que nous savons de toute façon correspondre.La complexité du cas le plus défavorable pour rechercher un motif se réduit à O (n) .

Exemple KMP

Algorithme

Cet algorithme est un processus en deux étapes. Nous créons d'abord un tableau auxiliaire lps [] et utilisons ensuite ce tableau pour rechercher le motif.

Prétraitement :

Nous pré-traitons le motif et créons un tableau auxiliaire lps [] qui est utilisé pour ignorer les caractères lors de la correspondance.
Ici, lps [] indique le préfixe correct le plus long qui est également le suffixe. Un préfixe approprié est le préfixe dans lequel la chaîne entière n'est pas incluse. Par exemple, les préfixes de la chaîne ABC sont “” , “A” , “AB” et “ABC” . Les préfixes appropriés sont “” , “A” et “AB” . Les suffixes de la chaîne sont “” , “C” , “BC” et “ABC” .

Recherche

Nous continuons à faire correspondre les caractères txt [i] et pat [j] et continuons à incrémenter i et j pendant que pat [j] et txt [i] continuent de correspondre.
Quand on voit une incompatibilité, on sait que les caractères pat [0..j-1] correspondent à txt [i-j + 1… i-1] . On sait aussi que lps [j-1] est le nombre de caractères de pat [0… j-1] qui sont à la fois préfixe et suffixe.À partir de cela, nous pouvons conclure que nous n'avons pas besoin de faire correspondre ces caractères lps [j-1] avec txt [ij… i-1] car nous savons que ces caractères va correspondre de toute façon.

Implémentation en 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

Sous licence CC BY-SA 3.0

Non affilié à Stack Overflow

algorithm
Algorithme Knuth Morris Pratt (KMP)

Recherche…

Introduction

Exemple KMP