(Rabin-Karp算法)比對字元串（滾動哈希）

Rabin-Karp算法的思路是将字元串的比較轉換成數字的比較。比較兩個長度為m的字元串是否相等需要O(m)的時間，而比較兩個數字是否相等通常可以是O(1)。為了将字元串映射到對應的數字，故此需要用到哈希函數。

接下來的問題是，如何快速将字元串映射到對應的數字呢？如果需要在 O(L)的時間内算出編碼，這種方法就沒有意義了，因為這個直接進行字元串比較需要的時間相同。為了能夠快速計算出字元串編碼，我們可以将字元串看成一個 26 進制的數（因為字元串中僅包含26個字母），它對應的 10 進制的值就是字元串的編碼值。

首先将字元轉換為 26 進制中的 0-25，即通過 arr[i] = (int)S.charAt(i) - (int)‘a’，可以将字元串 abcd 轉換為 [0, 1, 2, 3]，它對應的 10 進制值為：

我們将這個表達式寫得更通用一些，設 c[i]為字元串中第 i 個字元對應的數字，a = 26為字元串的進制，那麼有：

Rabin-Karp 算法用于多模式搜尋，常用于重複檢測和生物資訊學中尋找兩個或多個蛋白質的相似性。例如，判斷一個字元串中是否有重複的字元串出現或者一個字元串中是否包含另一個字元串就可以用Rabin-Karp 算法。

例如：

判斷s="abcdefghijkl"是否包含"bcde"子串？

利用上面公式先計算出"bcde"的哈希編碼，然後開始在字元串s中找，首先将字元轉換為 26 進制中的 0-25，即通過 arr[i] = (int)S.charAt(i) - (int)‘a’，可以将字元串 abcd 轉換為 [0, 1, 2, 3]，向右移動滑動視窗，從 abcd 變成 bcde，此時字元串對應的值從 [0, 1, 2, 3] 變成 [1, 2, 3, 4]，移除了最高位的 0，并且在最低位添加了 4，那麼我們可以快速地計算出新的字元串的編碼：

更通用的寫法是：

這樣，我們隻需要 O(L)的時間複雜度計算出最左側子串的編碼（即滑動視窗起始的編碼），這個O(L) 和滑動視窗的循環是獨立的。在滑動視窗向右滑動時，計算新的子串的編碼的時間複雜度僅為 O(1)。

在實際的編碼計算中，h0和h1的值可能會非常大，在 Java 語言中，會導緻整數的上溢出。一般的解決方法時，對編碼值進行取模，将編碼控制在一定的範圍内，防止溢出，即h = h % modulus。

h0對應的java代碼為：

h1對應的java代碼為：

hash = ((hash - arr[i - a] * Math.pow(g, a - 1) % MOD + MOD) % MOD * g % MOD + arr[i]) % MOD;  
 //a為滑動視窗的大小，需要比對的字元串的長度
           

Rabin-Karp算法的優勢

Rabin-Karp算法的優勢是可以多元度或者多模式的比對字元串。以多模式比對為例，如果需要在文本T中找出模式集合P=[P1, P2, …Pk]中所有出現的模式。對于這個問題，Rabin-Karp算法的威力就能發揮出來了，Rabin-Karp算法能通過簡單地擴充便能夠支援多模式的比對。

算法本質：按照k進制，進行編碼，資料太多了，就取模。實際應用中因為無法确定起始字元串的長度，常常與二分一起使用。

看完之後大家可以用這個題練習一下：leetcode 1044. 最長重複子串[困難]