KMP表构造算法

Question

我检查了维基百科中的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中的“部分匹配”表(又称“故障函数”)(维基百科上)

我想我现在知道答案了。不过，再解释一下还是有帮助的。谢谢!

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)

...