KMP DFA重新启动状态

Question

我指的是“Sedgewick &Wyane的算法第四版”第五章字符串匹配。

给出的算法是KMP子串搜索，它从模式状态建立DFA。我理解构建DFA的算法，代码如下：

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

        // build DFA from pattern
        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];     // Copy mismatch cases. 
            dfa[pat.charAt(j)][j] = j+1;   // Set match case. 
            x = dfa[pat.charAt(j)][x];     // Update restart state. 
        } 
    } 

我无法获得以下代码行：x = dfa[pat.charAt(j)][x]; // Update restart state.

我知道这个值是通过在部分构建DFA中提供pat1..j-1来实现的，但是无法获得代码，它是如何实现这一点的。

我还理解x是模式的最长前缀的长度，也是后缀。

我看到了许多其他相关的问题，但这些问题都与理解算法本身有关。

我需要理解x = dfa[pat.charAt(j)][x]; // Update restart state.是如何模拟重启状态的。

Answer 1

如果我们仔细观察，X被初始化为状态0，而J被初始化为状态1

现在，我们只是根据访问的下一个字符继续向前移动，因为X在J之后，他已经知道下一个是哪个状态，默认情况下，所有的都指向0，所以这条线将始终保持前缀，否则在0处重新开始

dfa[c][j] = dfa[c][x]; // Copy mismatch cases.此行只是创建failure或back pointers

前缀和此行将前缀向前移动，以便与J保持同步，因此它始终指向前缀== x = dfa[pat.charAt(j)][x]; // Update restart state.的位置

也许这将有助于进一步的https://labuladong.gitbook.io/algo-en/i.-dynamic-programming/kmpcharactermatchingalgorithmindynamicprogramming

Answer 2

首先，你应该知道X的含义：

在我们更新它之前，它意味着我们将从当前状态(j个字符matched)

• after我们更新它，它意味着我们将从下一个状态(j+1个字符matched)

)进入)的状态(成功匹配了多少个字符

然后

X的更新是由txti和patj的成功匹配引起的，注意，它们需要成功匹配的状态是什么(状态决定了这里的字符需要确定x=dfapat.charAt(J)的_ pat.charAt(j) _)，在第一次匹配失败的状态下，状态变成了原点X_，因为我们需要在search()中的下一个循环中匹配txti +1而不是txti。