algorithm => Алгоритм Кнут Моррис Пратт (KMP)

Вступление

KMP - это алгоритм сопоставления с образцом, который ищет появление «слова» W в основной «текстовой строке» S , используя наблюдение, что, когда происходит несоответствие, мы располагаем достаточной информацией, чтобы определить, где можно начать следующее совпадение. Мы используйте эту информацию, чтобы избежать совпадения символов, которые, как мы знаем, будут в любом случае соответствовать. Самая сложная сложность поиска шаблона сводится к O (n) .

КМР-пример

Алгоритм

Этот алгоритм является двухэтапным процессом. Сначала мы создаем вспомогательный массив lps [], а затем используем этот массив для поиска шаблона.

Предварительная обработка :

Мы предварительно обрабатываем шаблон и создаем вспомогательный массив lps [], который используется для пропуска символов при совпадении.
Здесь lps [] указывает на самый длинный правильный префикс, который также является суффиксом. Правильный префикс является префиксом, в котором целая строка не включена. Например, префиксы строки ABC - это «» , «A» , «AB» и «ABC» . Правильными префиксами являются «» , «A» и «AB» . Суффиксами строки являются «» , «C» , «BC» и «ABC» .

поиск

Мы сохраняем соответствующие символы txt [i] и pat [j] и продолжаем увеличивать i и j, пока pat [j] и txt [i] сохраняют соответствие.
Когда мы видим несоответствие, мы знаем, что символы pat [0..j-1] соответствуют txt [i-j + 1 ... i-1]. Мы также знаем, что lps [j-1] - количество символов pat [0 ... j-1], которые являются как правильным префиксом, так и суффиксом. Из этого можно заключить, что нам не нужно сопоставлять эти lps [j-1] символы с txt [ij ... i-1], потому что мы знаем, что эти символы будет соответствовать в любом случае.

Реализация в 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

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow

algorithm
Алгоритм Кнут Моррис Пратт (KMP)

Поиск…

Вступление

КМР-пример