string - Knuth-Morris-Pratt 算法中的 DFA 构造

我指的是 Sedgewick 的书“算法”(第 4 版)中用于子串搜索的 Knuth-Morris-Pratt (KMP) 算法的概要。

KMP 算法在基于确定性有限自动机 (DFA) 的子串搜索中使用备份。我了解 DFA 如何进入算法，但是我不明白如何构建 DFA，这是由以下代码片段完成的:

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];
}

其中 M 是模式的长度 pat 和 R 是字母表的大小。 charAt() 函数返回相应位置字符的整数值。

有人可以解释一下这段代码以何种方式构建了 dfa？我迷失在内部 for 循环的实际直观含义中。

最佳答案

让我们看看下面的 FA 模式 ACACAGA。





上图表示模式 ACACAGA 的图形和表格表示。

这里，DFA 中的状态数是 M + 1，其中 M 是模式的长度。构建 DFA 的主要内容是从当前状态为每个可能的字符获取下一个状态。给定一个字符 x 和一个状态 k，我们可以通过考虑字符串“pat[0..k-1]x”来获得下一个状态，它基本上是模式字符 pat[0], pat 1 ... pat[k- 1] 和字符 x。这个想法是获得给定模式的最长前缀的长度，使得前缀也是“pat[0..k-1]x”的后缀(LPS)。 length 的值给了我们下一个状态。

例如，让我们看看如何从上图中的当前状态 5 和字符“C”获取下一个状态。我们需要考虑字符串“pat[0..5]C”，即“ACACAC”。前缀为“ACACAC”后缀的模式的最长前缀的长度为4(“ACAC”)。因此，字符“C”的下一个状态(来自状态 5)是 4。

// dfa[i][j] = k denotes the transition function will go k'th state
// with character i from state j

// DFA will go always (i + 1)'th state from i'th state
//if the character c is equal to current character of pattern
dfa[pat.charAt(0)][0] = 1;

//  here X is initialized with LPS (longest prefix suffix)
// of pattern[0....j - 1]. LPS[0] is always 0
for (int X = 0; j = 1; j< M; j++) {
    for (int c = 0; c < R; c++) { // for all possible characters
        // transition function from j'th state taking character c
        // will go to the same state where it went from X(LPS)'th state
        // taking character c (justify it with an example)
        dfa[c][j] = dfa[c][X];
    }
    // DFA will go always (i + 1)th state from i'th state if
    // the character c is equal to current character of pattern
    dfa[pat.charAt(j)][j] = j + 1;
    X = dfa[pat.charAt(j)][X]; // update LPS
}

关于string - Knuth-Morris-Pratt 算法中的 DFA 构造，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30548170/