Rabin-Karp 演算法

把模式逐字元地對文字的每個視窗比較很慢，因為每次比較最多要 m 步。Rabin-Karp 把大多數這種完整比較換成單一廉價的數字比較：它先算出模式的短指紋（雜湊），再把一個同長的視窗滑過文字，隨時更新視窗的指紋，只有在兩個指紋相符時才費心比較實際字元。大多數視窗都在一步算術內被排除。

引擎是滾動雜湊。先在 O(m) 內算 h = hash(P)。接著算出第一個文字視窗 T[0..m-1] 的雜湊，再一格一格往前滾動，每次更新花 O(1)。在每個雜湊等於 h 的視窗，做一次逐字元的直接檢查以確認是真匹配並排除雜湊碰撞（兩個不同字串共享同一雜湊）。若雜湊不同，字串必定不同，於是完全跳過檢查。用一個好的隨機質數模數，假雜湊匹配很稀少，所以期望執行時間是 O(n+m)。然而最壞情況是 O(n*m)：對手輸入（或不走運的模數）可能讓每個視窗都碰撞，迫使每次都做完整檢查——所以 Rabin-Karp 帶有蒙地卡羅風味，它的速度是機率上的期望，不是保證。

Rabin-Karp 真正的超能力不在單模式搜尋（那裡 KMP 乾淨的最壞情況更可取），而在同時搜尋許多等長的模式：把所有模式雜湊進一個集合，然後每個文字視窗以 O(1) 期望時間對整個集合檢查。這使它天然適合抄襲偵測，以及在資料串流中尋找成千上萬個定長簽章中的任何一個。它也漂亮地推廣到二維模式比對（在大圖中找一張小圖）。只要記得那個驗證步驟——跳過它，會把一個可靠的演算法變成偶爾說謊的演算法。