KMP (Knuth-Morris-Pratt) 演算法是一個強力的字串搜尋演算法，能把原本暴力法的 O(m*n) 大刀一砍 [ 註1 ] 降成 O(m+n) !

字串搜尋，除了字面上的作用之外，在電腦科學中，還有各種應用，例如 基因搜尋啦、圖像比對 [ 註2 ] 等等

回到我們的主題，每個演算法都有自己的精神，而 KMP 的精神則是 :「重複的比對不做第二次」，這也是為何 KMP 能夠將乘法時間變成加法時間的關鍵

怎麼說呢？先來看看暴力法是麼做的吧~

Continue reading KMP — 字串搜尋演算法 →