KMP DFA前缀函数

我被要求了解KMP DFA，我在书中发现的是实现，但我们的讲师一直都在调用某些“前缀函数”。我真的不明白哪个部分是这个功能，有人可以向我解释吗？对不起，如果有人问我，但我找不到它。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; 
     } 
    } 
}

来源

2013-11-24 ashur

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的字符不匹配时，才使用此数组中的值。

Here是算法的明确实现（在Java中）。

来源

2013-11-24 23:04:22 yasen

谢谢，但据我所知存在KMP算法的两个版本（不过我可能是错的），你给我的链接称为标准算法，我已经实现了它，第二个是我知道FSM/DFA--这就是我的讲师所说的。我感到困惑：P – ashur

是的，有两种类型的KMP实施;使用DFA在这里介绍：https：//www.youtube.com/watch？v = iZ93Unvxwtw –

KMP DFA前缀函数

回答

相关问题