algorithm => Algorytm Knutha Morrisa Pratta (KMP)

Wprowadzenie

KMP jest algorytmem dopasowywania wzorców, który wyszukuje wystąpienia „słowa” W w głównym „ciągu tekstowym” S , wykorzystując spostrzeżenie, że w przypadku niezgodności mamy wystarczające informacje, aby ustalić, gdzie może rozpocząć się następne dopasowanie. skorzystaj z tych informacji, aby uniknąć dopasowania znaków, o których wiemy, że i tak będą pasować. W najgorszym przypadku złożoność wyszukiwania wzorca zmniejsza się do O (n) .

Przykład KMP

Algorytm

Algorytm ten jest procesem dwuetapowym. Najpierw tworzymy tablicę pomocniczą lps [], a następnie używamy tej tablicy do wyszukiwania wzorca.

Wstępne przetwarzanie :

Wstępnie przetwarzamy wzorzec i tworzymy pomocniczą tablicę lps [], która służy do pomijania znaków podczas dopasowywania.
Tutaj lps [] wskazuje najdłuższy właściwy przedrostek, który jest również przyrostkiem. Właściwym przedrostkiem jest przedrostek, w którym nie jest zawarty cały ciąg. Na przykład przedrostki ciągu ABC to „” , „A” , „AB” i „ABC” . Prawidłowe prefiksy to „” , „A” i „AB” . Sufiksy ciągu to „” , „C” , „BC” i „ABC” .

Badawczy

Ciągle dopasowujemy znaki txt [i] i pat [j] oraz stale zwiększamy i i j, podczas gdy pat [j] i txt [i] nadal pasują.
Kiedy widzimy niedopasowanie, wiemy, że znaki pat [0..j-1] pasują do txt [i-j + 1… i-1]. Wiemy również, że lps [j-1] jest liczbą znaków pat [0… j-1], które są zarówno poprawnym przedrostkiem, jak i przyrostkiem. Z tego możemy wywnioskować, że nie musimy dopasowywać tych znaków lps [j-1] do txt [ij… i-1], ponieważ wiemy, że te znaki i tak będzie pasować.

Implementacja w Javie

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

Licencjonowany na podstawie CC BY-SA 3.0

Nie związany z Stack Overflow

algorithm
Algorytm Knutha Morrisa Pratta (KMP)

Szukaj…

Wprowadzenie

Przykład KMP