瞭解Knuth Morris Pratt（KMP）失敗函數

我一直在閱讀Wikipedia article about the Knuth-Morris-Pratt algorithm，我對如何在跳轉/部分匹配表中找到值感到困惑。瞭解Knuth Morris Pratt（KMP）失敗函數

i | 0 1 2 3 4 5 6 
W[i] | A B C D A B D 
T[i] | -1 0 0 0 0 1 2

如果有人能更清楚地說明快捷規則，因爲這句話

「讓我們說，我們發現了一個合適的後綴這是一個適當的前綴和結束在W [2]長度爲2 （最大可能）「

令人困惑。如果W [2]後面的正確後綴不是3的大小？

我也想知道爲什麼T [4]不爲1時，有大小爲1的前綴和後綴：A.在

感謝，可以提供任何幫助。

來源

2013-02-06 Shaun

注意失敗函數T [i]不使用i作爲索引，而是使用長度。因此，T [2]表示由W的前兩個字符形成的字符串的最長正確邊界（既是前綴又是後綴的字符串）的長度，而不是由以字符結尾的字符串形成的最長正確邊界2.這就是爲什麼T [2]的最大可能值是2而不是3 - 由W的前兩個字符形成的子串不能具有大於2的長度。

使用這個解釋，它也是更容易看出爲什麼T [4]是0而不是1.由W的前四個字符組成的W的子字符串是ABCD，它沒有合適的前綴，也是一個合適的後綴。

希望這會有所幫助！

來源

2013-02-06 20:40:47 templatetypedef

好吧，幫助很多。您是否也可以幫助澄清快捷方式規則的工作原理？ – Shaun

@ Shaun-你的意思是「快捷規則」？我對KMP很熟悉，但從未聽過這個詞。 – templatetypedef

從我的理解中，它利用T [i]的前一個值來計算當前值。我想知道它是如何完成的。 – Shaun

「讓我們說，我們發現了一個合適的後綴這是一個適當的前綴和結束在W [2]長度爲2（最大可能）」

好吧，長度可以最多2，它是正確的，這是爲什麼...... 一個事實：「正確的」前綴不能是整個字符串，同樣適用於「正確的」後綴（如正確的子集）

Lets，W [0] = AW [1] = AW [2] = A，即模式爲「AAA」，因此，（最大長度）適當前綴可以是「AA」（從左到右），並且（最大長度）適當後綴可以是「AA」（從右到左） //是的，前綴和後綴有重疊（中間的「A」）

因此，該值將是2而不是3，只有前綴不正確時，該值纔會爲3。

來源

2014-07-02 20:09:48

瞭解Knuth Morris Pratt（KMP）失敗函數

回答

相關問題