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) 

...