KMP DFA重新启动状态

Question

我指的是"Sedgewick&Wyane的算法第四版"字符串匹配第5章。

给出的算法是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中输入pat[1..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

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

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

Answer 2

首先，您应该知道X:的含义

• 在我们更新它之前，它意味着我们将从当前状态(匹配了j个字符(转到的状态(成功匹配了多少个字符(
• 更新后，这意味着我们将从下一个状态进入(j+1个字符匹配(

然后

X的更新是由txt[i]和pat[j]的成功匹配引起的，注意，它们需要什么状态才能成功匹配(状态决定了X，这里需要的字符决定了X=dfa[pat.charAt(j(][X]的pat.charAt，因为我们需要在search((的下一个循环中匹配txt[i+1]而不是txt[i]