相关疑难解决方法(0)

我指的是Sedgewick的书"Algorithms"(第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循环的实际直觉意义上.

我一直在阅读关于Knuth-Morris-Pratt算法的维基百科文章,我对如何在跳转/部分匹配表中找到值感到困惑.

  i  |  0  1  2  3  4  5  6
W[i] |  A  B  C  D  A  B  D
T[i] | -1  0  0  0  0  1  2

如果有人可以更清楚地解释因为句子的快捷方式规则

"让我们说我们发现了一个正确的后缀,它是一个正确的前缀,结束于W [2],长度为2(最大可能)

令人困惑.如果正确的后缀在W [2]结束,它的大小不是3吗？

另外我想知道为什么T [4]在没有大小为1的前缀和后缀时不是1:A.

感谢您提供的任何帮助.