基於DFA的KMP實施是否比標準實施更高效？

Question

基於KMP算法的確定性有限狀態自動機的複雜度是多少？它是否比KMP算法的標準非自動化版本更高效？

class KMP { 
    private final int R;  
    private int[][] dfa;  

    private String pat;  

    public KMP(String pat) { 
    this.R = 256; 
    this.pat = pat; 

    int M = pat.length(); 
    dfa = new int[R][M]; 
    dfa[pat.charAt(0)][0] = 1; 
    for (int X = 0, j = 1; j < M; j++) { 
     for (int c = 0; c < R; c++) 
      dfa[c][j] = dfa[c][X];  
     dfa[pat.charAt(j)][j] = j+1; 
     X = dfa[pat.charAt(j)][X];  
    } 
    } 

    public int search(String txt) { 
    int M = pat.length(); 
    int N = txt.length(); 
    int i, j; 
    for (i = 0, j = 0; i < N && j < M; i++) { 
     j = dfa[txt.charAt(i)][j]; 
    } 
    if (j == M) return i - M;  
    return -1;     
    } 
} 

測試：

// test KMP DFA 
KMP p = new KMP("abacab"); 
System.out.println("KMPDfa: " + p.search("ababbadabacabcbabac")); 
output: 7 

Answer 1

我相信，KMP的標準版本是更有效，因爲它使用較少的內存，則DFA版本。如果您有大字母和大圖案，DFA數組可能會變得相當大。

這兩個版本的實現可以在流動鏈接中找到，它們在相關課程頁面中有很好的文檔說明（請注意，在給定的鏈接中，KMPplus是標準版本）。

http://algs4.cs.princeton.edu/53substring/KMP.java.html http://algs4.cs.princeton.edu/53substring/KMPplus.java.html