KMP DFA состояние перезапуска - PullRequest
Новая
       26

KMP DFA состояние перезапуска

0 голосов
/ 01 апреля 2020

Я имею в виду «Алгоритмы четвертого издания Sedgewick & Wyane» Соответствие строк Глава 5.

Данный алгоритм представляет собой поиск подстроки KMP, в котором он создает DFA из состояния шаблона. Я понимаю алгоритм построения DFA, код выглядит следующим образом: 

public KMP(String pat) {
        this.R = 256;
        this.pat = pat;

        // build DFA from pattern
        int m = pat.length();
        dfa = new int[R][m]; 
        dfa[pat.charAt(0)][0] = 1; 
        for (int x = 0, j = 1; j < m; j++) {
            for (int c = 0; c < R; c++) 
                dfa[c][j] = dfa[c][x];     // Copy mismatch cases. 
            dfa[pat.charAt(j)][j] = j+1;   // Set match case. 
            x = dfa[pat.charAt(j)][x];     // Update restart state. 
        } 
    }

Я не могу получить следующую строку: x = dfa[pat.charAt(j)][x]; // Update restart state.

Я понимаю, что это значение достигается с помощью кормление патом [1..j-1] при частичной сборке DFA, но не в состоянии получить тот код, как он этого добивается.

Я также понимаю, что x - это длина самого длинного префикса шаблона, который также является суффиксом.

Я видел много других связанных вопросов, но они связаны с пониманием самого алгоритма.

Мне нужно понять, как x = dfa[pat.charAt(j)][x]; // Update restart state. имитирует состояние перезапуска.

...