algorithm - KMP建表算法

Question

我检查了 KMP table-building algorithm from Wikipedia但是我不明白 while 循环的第二种情况背后的逻辑

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

我尝试使用此算法构建一个表并且它运行良好。我知道 cnd ← T[cnd] 有助于找到合适的后缀长度。我不明白的是它“如何”做到这一点？

最好有一个例子来解释。

谢谢!

编辑:我刚刚发现我的问题与这里的问题重复:"Partial match" table (aka "failure function") in KMP (on wikipedia)

我想我现在得到了答案。尽管如此，多一个解释还是有帮助的。谢谢!

Answer 1

假设你有一个字符串 Hello World!!!并且您想搜索 Head Up .

Hello World!!!
Head Up
  ^

当您处于第一个和第二个字符时，第一个条件适用 (first case: the substring continues) ，在标记位置的情况下，字符不匹配但是你已经在一个子字符串匹配中(2个字符匹配到那里)，这种情况对应第​​二个条件(second case: it doesn't, but we can fall back) .第三种情况是您未匹配模式的第一个字符。

第二个条件是必要的，因为你可以使用匹配字符的信息直到未匹配，以避免不必要的比较你已经知道结果(跳过你已经知道开头部分的string的字符模式将不匹配)。

示例:使用字符串 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)

...