2

我指的是“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.模拟重启状态。

4

2 回答 2

0

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

现在，我们只是根据访问的下一个字符继续向前移动，并且由于 X 在 J 后面，他已经知道下一个状态，默认情况下ALL ARE POINTING BACK TO 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

于 2021-06-25T05:42:13.687 回答
0

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

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

然后

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

于 2021-10-17T10:36:33.590 回答