algorithm - KMP 中的 "Partial match"表(又名 "failure function")(在维基百科上)

Question

我正在阅读 KMP algorithm在维基百科上。在“建表算法伪代码说明”一节中有一行代码让我很困惑:let cnd ← T[cnd]

它有一个注释:(第二种情况:它没有，但我们可以回退)，我知道我们可以回退，但是为什么T[cnd]，有什么原因吗？因为这真的让我很困惑。

完整的建表算法伪代码如下:

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next 
character of the current candidate substring)

    (the first few values are fixed but different from what the algorithm 
might suggest)
    let T[0] ← -1, T[1] ← 0

    while pos < length(W) do
        (first case: the substring continues)
        if W[pos - 1] = W[cnd] then
            let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        else if cnd > 0 then
            let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        else
            let T[pos] ← 0, pos ← pos + 1

Answer 1

你可以回退到 T[cnd] 因为它包含模式 W 的前一个最长正确前缀的长度，这也是 的正确后缀>W[0...cnd]。因此，如果 W[pos-1] 处的当前字符与 W[T[cnd]] 处的字符匹配，则可以扩展 的最长适当前缀的长度>W[0...pos-1](这是第一种情况)。

我猜这有点像动态规划，您依赖于先前计算的值。

This 解释可能对您有所帮助。