KMP算法最佳情況下的最小比較次數是多少？

KMP算法最佳情況下的最小比較次數是多少？KMP算法最佳情況下的最小比較次數是多少？

2012-10-20 Ansari

0，如果你正在搜索的字符串是空的。想不到比這更好的場景。 – rici

它不是常數，它的O（n）其中n是文本的長度，文本長度爲0，因此n = 0. – Ansari

在這種情況下，它顯然爲0，但O（n）與n不同。例如，n + k（對於任何常數k）是O（n）。 O（n）僅*是關於限制的聲明，而不是關於n的特定值的聲明。無論如何，KMP肯定是O（n），但在大多數情況下，乘數（對於比較數）略低於1.0。 – rici

那麼，在最好的情況下比較的最小數量將是你的字符串的長度，這意味着你找到了匹配的第一次嘗試。該算法是O（n），這意味着上限或最壞情況將需要n個比較，其中n是您正在搜索的字符串的長度。這個wiki很不錯。 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

來源

2012-10-20 21:56:22 DaveyLaser

我的答案是：如果T是一個字符串，P是一個模式，其中| T | = n，| P | = m，如果總的移位數爲S，那麼至多移位爲m-1，並且所需的最小移位數爲1，如果總比較數爲n，則總數將爲O（n + S）是1，而不是O（n）。例如，如果T = xxa，並且P = xx，那麼比第一次嘗試執行1個算法停止的移位並且總比較將是3（2代表'xx'和1代表不匹配）........ ...如果我錯了，請糾正我。 – Ansari

是啊！ :)看起來是正確的。 – DaveyLaser

您的示例中不會出現不匹配的情況，因爲P只有兩個字符 – alestanis

當您正在查找的字符串位於您的文本字符串的開頭時，會發生最好的情況。在這種情況下，如果您正在尋找一個n字母串中的k字母串，則最佳的比較次數爲k。

根據您的k字母詞，您還必須考慮計算表的開銷，如果找不到匹配項，您可以知道要跳過哪些字母。在任何情況下，這種構造都在O(k)中完成。

來源

2012-10-20 21:55:23 alestanis

說，我有一個文本和圖形等： T = xxabc P = XX 在這種情況下串長度是5和模式長度爲2時，小於總的比較是4.難道是最好的情況下，因爲它不看起來像O（m） – Ansari

四個比較在哪裏？你比較T [0]到P [0]然後T [1]到P [1]，你就完成了。 – alestanis

KMP算法最佳情況下的最小比較次數是多少？

回答

相關問題