KMP DFA prefix function

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, сокращенную для «fail link», потому что, выполняя сопоставление, мы используем значения в этом массиве только тогда, когда символы от text и pattern не совпадают.

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