java - 这种基于DFA的KMP实现是否比标准实现更有效？

这种基于确定性有限状态自动机的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

最佳答案

我相信KMP的标准版本效率更高，因为它使用的内存少于DFA版本。如果您有一个大字母和一个大图案，则DFA数组可能会变得非常大。

可以在流动的链接中找到两个版本的实现，同时在相关的课程页面中找到了关于它们如何工作的很好的文档（请注意，在给定的链接中，KMPplus是标准版本）。

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

关于java - 这种基于DFA的KMP实现是否比标准实现更有效？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5628713/