KMP字符串搜索算法的最壞情況是什麼？

任何人都可以建議我最糟糕的情況下「文本字符串 - 模式對」測試KMP算法實現？KMP字符串搜索算法的最壞情況是什麼？

2011-10-20 Mustafa Zengin

KMP具有線性運行時複雜性，因此任何具有目標的字符串都將在最差情況下運行。並且你的實現是一個multifind，那麼每個case都是以線性時間運行的。 – davin

我會在這裏寫下我的答案，因爲問題是關閉的：在他們的論文「字符串中的快速模式匹配」Knuth，Morris和Pratt證明算法的最壞情況是斐波那契字符串定義爲 $ \ phi_1 = b， \ phi_2 = b，\ phi_n = \ phi_ {n-1} \ phi_ {n-2} $檢查第5節。本文的理論考慮。 –

我會說喜歡

xx........x 
| n times |

的模式和像

xxx.........xyx...........xy.... 
| n-1 times | | n-1 times |

字符串將是最糟糕的情況之一，但它仍然O(m+n)

來源

2011-10-20 16:48:50

你的意思是'O（n + m）' – davin

@davin正確，糾正 –

每當發生不匹配時，我們根據前綴後綴匹配表繼續將模式字符指針移動到左側。對於每個y字符的答案中的例子，我們發現不匹配，並且我們一直在左移一個字符模式1字符的字符指針。如果在文本中有c1個x字符和沒有y字符的c2個，我們得到的比較總數是（c1 + c2 *模式大小）。我對嗎？ –

你可以找到關於KMP算法這裏什麼：

KMP ALGORITHM

快速提取物：

高德納，莫里斯和Pratt發現按照第一線性時間字符串匹配算法對樸素算法進行嚴格的分析。 Knuth-Morris-Pratt算法保留在文本掃描期間收集的天真方法浪費的信息。通過避免這種浪費信息，它實現了O（n + m）的運行時間，這在最壞的情況下是最佳的。 也就是說，在最壞的情況下，Knuth-Morris-Pratt 算法我們必須至少檢查文本中的所有字符和模式。

你應該能夠驗證你對算法的理解，並找到你需要的東西。

希望它有助於

來源

2011-10-20 16:47:36

KMP字符串搜索算法的最壞情況是什麼？

回答

相關問題