Функция префикса KMP DFA

Question

Меня попросили узнать о KMP DFA, и то, что я нашел в своей книге, - это реализация, но наш лектор все время вызывает что-то "префиксную функцию". Я действительно не могу понять, какая часть этой функции здесь, кто-то может мне это объяснить? Извините, если это где-то спросили, но я не смог его найти.

public class KMP {
private String pat;
private String t;
private int[][] fsm;

public static final int ALPHABET = 256;

public KMP(String pat) {
    this.pat = pat;
    char[] pattern = pat.toCharArray();

    int M = pattern.length;

    fsm = new int[ALPHABET][pattern.length];
    fsm[pattern[0]][0] = 1;

    for(int X = 0, j = 1; j < M; j++) {

        for(int c = 0; c < ALPHABET; c++) {
            fsm[c][j] = fsm[c][X];
        }
        fsm[pattern[j]][j] = j + 1;
        X = fsm[pattern[j]][X];
    }
    display(fsm);
}

public void search(String t) {
    char[] text = t.toCharArray();
    this.t = t;
    int N = text.length;
    int M = pat.length();

    int i, j;
    for(i = 0, j = 0; i < N; i++) {
        j = fsm[t.charAt(i)][j];
        if(j == M) {
            System.out.println("Found at " + (i - M + 1));
            j = 0;
        }
    }
}

Answer 1

Алгоритм KMP не создает DFA. То, что вы реализовали, больше похоже на DFA, который распознает некоторую строку pattern,

Идея алгоритма KMP состоит в том, чтобы построить так называемую префиксную функцию для заданного pattern, И что это за функция? Это определение заключается в том, что для каждой позиции i из строки мы заинтересованы в длине самого длинного суффикса pattern[1..i], который также является префиксом pattern строка (с 0 индексами). Это может показаться странным, но вот пример:

Префиксная функция pattern = "abacabacada" является pf[] = 0 0 1 0 1 2 3 4 5 0 1, pf[8] равно 5, потому что самый длинный суффикс "bacabaca", то есть также префикс "abacabacada" - это "abaca", длина которого равна 5. Аналогично, pf[9] = 0 потому что нет суффикса bacabacad который также является префиксом abacabacada (шаблон).

Я надеюсь, что это объяснение делает функцию префикса более понятной. Некоторые друзья вызывают массив, сохраняя функцию префикса fl, сокращение от "ошибка ссылки", потому что при сопоставлении мы используем значения в этом массиве только тогда, когда символы из text а также pattern несоответствие.

Вот четкая реализация алгоритма (на Java).