這篇是我學習 Rabin–Karp (Karp–Rabin) 演算法的一個紀錄。

推薦讀者要先有滑動窗口、hash collision(雜湊衝突)等演算法觀念再來閱讀。

Rabin–Karp（或 Karp–Rabin）演算法介紹

這個演算法的名字其實就是由發明者的名字 Michael O. Rabin 和 Richard M. Karp 來命名，所以標題的兩種演算法名稱都正確。

主要概念是透過 Rolling Hash(中文翻譯叫旋轉雜湊) 的雜湊函式，先計算兩個比對字串的 hash 值後，再比對兩個 hash 值是否相等，相等就有可能兩個字串一樣，不一樣可以透過滑動窗口的演算法，窗口內的字串中，移除最左字元，加入最右字元，更新 hash 值，然後再和要搜尋字串的 hash 值做比對，因為比對 hash 值的過程只是比較數字，可以不用將兩個字串都從頭遍歷，更新 hash 值也是不用，因此可以加速字串的搜尋。

hash 值求值舉例說明

我們用 LeetCode 2156. Find Substring With Given Hash Value 題目提到的雜湊函式來舉例：

• s 代表的是一個字串，然後 val(s[i]) 代表一個字元經轉換後的數值，這題是這樣轉換的，a 為 1、b 為 2、c 為 3...y 為 25、z 為 26。
• p 代表的是基數(base)。
• m 代表的是模數（modulo），通常選大質數，防止 hash collision，但計算比較吃力，取模是避免前面的乘積太大。

題目給的範例 1 中，s = 'ee'、p = 7、m = 20，故hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0，0 就是這個段落要求的 hash 值。

在求得 hash 值後會和另外一個 hash 值做比較，而這另外一個 hash 值也是從一個字串計算而來，所以若兩個值相同，在沒有發生 hash collision 的情況下，兩個字串就會相等。

由於可能會存在 hash collision 的可能，因此在 hash 值相等時，我們需要再額外判斷其是否真正相等，這個可能性可以透過前面提到的 m 模數降低機率。

所以舉個例子，s = "leetcode"，"ee" 字串我們已經知道 hash 值為 0，假設要在字串內找到 "od"，(15 * 1 + 4 * 7) mod 20 = 43 mod 20 = 3，兩個 hash 值不相同，所以要繼續搜尋其他子字串。

更新怎麼做？

這裡我承認偷懶了XD，直接取用 ChatGPT 的回答：

時間複雜度分析

透過以上 hash 值的求值過程，假設有一個長度為 n 的主要字串，還有一個長度為 m 的子字串，我們可以知道：

初始 hash 值計算是 O(m)，更新只需要 O(1)，然後遍歷主要字串，會搜尋 n − m + 1 個子字串，為 O(n)，所以平均情況下是 O(n + m)。

最壞情況是常發生雜湊碰撞，時間複雜度退回 O(n * m)，故需要設計良好的雜湊函數。

適合可以同時搜尋多個字串、大量字串搜尋的情況。

參考資源

Rabin Karp - Shortest Palindrome - Leetcode 214

LeetCode 練習題

214. Shortest Palindrome

2156. Find Substring With Given Hash Value