KMP算法中使用的故障功能是如何工作的？

Question

我已經盡最大努力閱讀了大部分關於這方面的文獻，並且仍然沒有理解如何構造KMP算法中使用的失效函數。我一直主要提到http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching教程，大多數人認爲這很好。但是，我仍然沒有理解它。如果你能夠給我一個簡單易懂的解釋，我會很感激。

Answer 1

失敗函數實際上告訴我們：如果你匹配一個字符串的X個字符，那麼這個字符串的最長後綴是什麼，這也是一個搜索字符串的前綴。

你在問它是如何構建的，這種方法非常簡單。

如果在字符串的末尾添加一個新字符，那就是構建f [x]，如果它與位置f [x-1]上的字符相匹配，那麼f [x]就是f [X-1] +1。

在其他不匹配的情況下，您會嘗試查找更小和更小的後綴並檢查它們是否匹配。

例如，您有一個詞"accadaccac"正在爲其建立故障功能，並且您剛剛添加了字母'c'。假設您正在爲最後一個字母'c'構建失敗函數。

• 首先，你檢查以前的信件的功能失效，其故障作用是4，因爲你可以用前綴匹配"acca"後綴"acca"，現在你添加字母'c'，它不匹配字母'd'成功的前綴"acca"。
• 所以你回溯到最後的好後綴。您現在正在搜索後綴"acca"，它也是"accadaccac"的前綴，但小於「acca」。這個問題的答案是f [長度（「acca」） - 1]或f [3]，即f [3] = 1，因爲長度爲1的後綴（只是字母'a'）也是一個前綴搜索字符串。
• 現在你可以嘗試如果'c'與位置1上的字符匹配，並且瞧，它匹配，所以現在你知道f [9] = f [f [8] -1] +1 = 2。

我希望這會幫助你。祝你好運！ :)

Answer 2

http://www.oneous.com/Tutorial-Content.php?id=24

U可以利用學習資源本網站對於理解KMP算法和故障功能。也可以嘗試使用代碼並手動對其進行一些運行。然而，理解其工作的最好方法是自己編寫一些基本算法的變體。我建議你從SPAY的NHAY和PERIOD開始。