KMP模式匹配算法時間複雜度可以是O（m * n）？

Question

我在這裏看到了很少的答案，但仍需要一些澄清。 KMP具有O(n+m)最壞情況下的時間複雜度。但是我的理解是，在最壞的情況下，它應該是O(n*m)。讓我們舉個例子：

string(n): aaaaaaaaa 
pattern(m): aaab 

前3個字符匹配。然後是不匹配的。適當的"aaa"前綴後綴表將返回2.因此只有（3-2）= 1字符移動可以根據KMP進行。因此，我們比較n*(m-1)次，然後才能斷定在這種情況下不存在匹配。有效的時間複雜度是O(n*m)。

有人可以請解釋在這種情況下它是怎麼樣的O(m+n)。除了正確的前綴後綴表之外，我還必須考慮其他任何事情，並將其視爲一種特殊情況。是否在KMP中提到過？對這個特定場景的詳細解釋會非常有幫助。

Answer 1

所以只有（3-2）= 1的字符移動可以根據KMP進行。

是的。

因此，我們比較n *（m-1）次，然後才能斷定在這種情況下不存在匹配。

號 我們比較接下來的事情是a針對a（圖案的第3次），這給2 + 1 = 3作爲當前匹配的長度（文字的第4次）。

---

讓我們的工作T = aaaaaaaaa文字和P = aaab模式的例子。

• 在位置1中，我們有T [1] = P [1]，所以匹配的長度爲1。
• 在位置2時，我們有T [2] = P [2]，所以比賽的長度是2.
• 在位置3，我們有T [3] = P [3]，所以比賽的長度是3.
• 在位置4，我們有T [4] ≠ P [4]。 匹配的長度降低爲pref（3）= 2（負步）。
• 再次在位置4上，我們有T [4] = P [3]，所以匹配的長度是3.
• 在位置5上，我們有T [5] ≠ P [4]。 匹配的長度降低爲pref（3）= 2（負步）。
• 再次在位置5上，我們有T [5] = P [3]，所以匹配的長度是3.
• 依此類推。

正如您所看到的，從位置4開始，對於每個位置，我們分兩步而不是一步。 但是我們並沒有在任何時候比較子串，只是個別的字符。 位置數爲| T |，負階數最多爲| T |，因此總階數相對於| T |是線性的。