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前綴函數

回答

相關問題