java - 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 (模式)的前缀。

我希望这个解释能使前缀功能更清楚。有 friend 称数组，存储前缀函数fl，"fail link"的简称，因为我们在做匹配时，只有当text中的字符时，我们才使用这个数组中的值> 和 pattern 不匹配。

Here是算法的明确实现(在 Java 中)。