有人要求我了解 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;
}
}
}
最佳答案
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 中)。
关于java - KMP DFA前缀函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20169631/