我正在阅读 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
最佳答案
你可以回退到 T[cnd]
因为它包含模式 W 的前一个最长正确前缀的长度,这也是 的正确后缀>W[0...cnd]
。因此,如果 W[pos-1]
处的当前字符与 W[T[cnd]]
处的字符匹配,则可以扩展 的最长适当前缀的长度>W[0...pos-1]
(这是第一种情况)。
我猜这有点像动态规划,您依赖于先前计算的值。
This 解释可能对您有所帮助。
关于algorithm - KMP 中的 "Partial match"表(又名 "failure function")(在维基百科上),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18911735/