2
KMP(Knuth-Morris-Pratt)算法比簡化的Boyer-Moore算法執行的比較次數少嗎?KMP算法比簡化的Boyer-Moore算法執行的比較少嗎?
KMP(Knuth-Morris-Pratt)算法比簡化的Boyer-Moore算法執行的比較次數少嗎?KMP算法比簡化的Boyer-Moore算法執行的比較少嗎?
的Boyers Moore算法通常應以較少的比較執行從here
報價應該相當清楚的是,如果是正常,一個給定的字母犯規出現在所有的搜索字符串的情況下,那麼這個算法只需要大約N/M個字符比較(N =長度(s1),M =長度(s2)) - 對KMP算法有很大改進,但仍然需要N.但是,如果不是這種情況,那麼我們可能需要再次進行N + M比較(使用算法的完整版本)。幸運的是,對於許多應用程序,我們接近N/M性能。如果搜索字符串非常大,那麼它可能會出現一個給定的字符,但與其他算法相比,我們仍然有一個很好的改進(如果字符隨機分佈在一個字符串中,大約N * 2/alphabet_size)。
我在很多年前做了一些測試。 B-M每次都贏得KMP。 – EJP 2017-09-06 02:08:36