KMP表构建算法

Question

KMP表构建算法

algorithmpattern-matchingknuth-morris-pratt

3

我查看了维基百科上的KMP表构建算法，但我不理解while循环的第二种情况背后的逻辑。

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

我尝试使用这个算法构建表格，它完美地工作。我理解cnd ← T[cnd]有助于找到正确的后缀长度。但我不明白它是如何做到的？

带有示例的解释会很好。

谢谢！

编辑：我刚发现我的问题是这里的一个重复问题："KMP中的“部分匹配”表（又名“失败函数”）(维基百科)"。

我想我现在得到了答案。不过，再解释一下会更有帮助。谢谢！

- Naruto Uzumaki

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NetVipeC · Accepted Answer

假设你有一个字符串Hello World!!!，你想搜索Head Up。

Hello World!!!
Head Up
  ^

当您在第一和第二个字符时，第一个条件适用（第一种情况：子字符串继续），在标记位置的情况下，字符不匹配但您已经在子字符串匹配中（到此为止匹配了2个字符），这种情况对应于第二个条件（第二种情况：它不匹配，但我们可以回退）。第三种情况是当您不匹配模式的第一个字符时。

第二个条件是必要的，因为您可以使用匹配字符直到不匹配的信息，以避免不必要的比较，您已经知道结果（跳过字符串中您已经知道起始部分与模式不匹配的字符）。

例如：对于字符串HeHello World!!!并搜索Hello。

HeHello World!!!
Hello
  ^ when you miss match this character using the table of KMP you known that 
    could skip 2 characters because

HeHello World!!!
 Hello
 ^ this would miss match

在构建"HeHello"的模式表时，假设"^"表示"cnd"，"*"表示"pos"。起始点为"pos = 2"和"cnd = 0"（但在检查模式时，是使用"pos - 1 = 1"）。

HeHeHello     T [-1,0,0,0,0,0,0,0,0]
^* comparing 0 with 1 go to condition 3        cnd = 0, pos = 2
                        _
HeHeHello     T [-1,0,0,1,0,0,0,0,0]
^ * comparing 0 with 2 go to condition 1       cnd = 0, pos = 3
                          _
HeHeHello     T [-1,0,0,1,2,0,0,0,0]
 ^ * comparing 1 with 3 go to condition 1      cnd = 1, pos = 4
                            _
HeHeHello     T [-1,0,0,1,2,3,0,0,0]
  ^ * comparing 2 with 4 go to condition 1     cnd = 2, pos = 5
                              _
HeHeHello     T [-1,0,0,1,2,3,4,0,0]
   ^ * comparing 3 with 5 go to condition 1    cnd = 3, pos = 6

HeHeHello     T [-1,0,0,1,2,3,4,0,0]
    ^ * comparing 4 with 6 go to condition 2 (cnd = T[cnd], cnd = T[4] = 2)

HeHeHello     T [-1,0,0,1,2,3,4,0,0]
  ^   * comparing 2 with 6 go to condition 2 (cnd = T[cnd], cnd = T[2] = 0)

...