由淺入深理解Rabin-Karp算法

經(jīng)常有讀者留言，請我講講那些比較經(jīng)典的算法，我覺得有這個必要，主要有以下原因：

1、經(jīng)典算法之所以經(jīng)典，一定是因為有獨特新穎的設(shè)計思想，那當然要帶大家學習一波。

2、我會盡量從最簡單、最基本的算法切入，帶你親手推導出來這些經(jīng)典算法的設(shè)計思想，自然流暢地寫出最終解法。一方面消除大多數(shù)人對算法的恐懼，另一方面可以避免很多人對算法死記硬背的錯誤習慣。

我之前用狀態(tài)機的思路講解了KMP 算法，說實話 KMP 算法確實不太好理解。不過今天我來講一講字符串匹配的另一種經(jīng)典算法：Rabin-Karp 算法，這是一個很簡單優(yōu)雅的算法。

本文會由淺入深地講明白這個算法的核心思路，先從最簡單的字符串轉(zhuǎn)數(shù)字講起，然后研究一道力扣題目，到最后你就會發(fā)現(xiàn) Rabin-Karp 算法使用的就是滑動窗口技巧，直接套前文講的滑動窗口算法框架就出來了，根本不用死記硬背。

廢話不多說了，直接上干貨。

首先，我問你一個很基礎(chǔ)的問題，給你輸入一個字符串形式的正整數(shù)，如何把它轉(zhuǎn)化成數(shù)字的形式？很簡單，下面這段代碼就可以做到：

strings="8264";
intnumber=0;
for(inti=0;i//將字符轉(zhuǎn)化成數(shù)字
number=10*number+(s[i]-'0');
print(number);
}
//打印輸出：
//8
//82
//826
//8264

可以看到這個算法的核心思路就是不斷向最低位（個位）添加數(shù)字，同時把前面的數(shù)字整體左移一位（乘以 10）。

為什么是乘以 10？因為我們默認探討的是十進制數(shù)。這和我們操作二進制數(shù)的時候是一個道理，左移一位就是把二進制數(shù)乘以 2，右移一位就是除以 2。

上面這個場景是不斷給數(shù)字添加最低位，那如果我想刪除數(shù)字的最高位，怎么做呢？比如說我想把 8264 變成 264，應該如何運算？其實也很簡單，讓 8264 減去 8000 就得到 264 了。

這個 8000 是怎么來的？是 8 x 10^3 算出來的。8 是最高位的數(shù)字，10 是因為我們這里是十進制數(shù)，3 是因為 8264 去掉最高位后還剩三位數(shù)。

上述內(nèi)容主要探討了如何在數(shù)字的最低位添加數(shù)字以及如何刪除數(shù)字的最高位，用R表示數(shù)字的進制數(shù)，用L表示數(shù)字的位數(shù)，就可以總結(jié)出如下公式：

/*在最低位添加一個數(shù)字*/
intnumber=8264;
//number的進制
intR=10;
//想在number的最低位添加的數(shù)字
intappendVal=3;
//運算，在最低位添加一位
number=R*number+appendVal;
//此時number=82643

/*在最高位刪除一個數(shù)字*/
intnumber=8264;
//number的進制
intR=10;
//number最高位的數(shù)字
intremoveVal=8;
//此時number的位數(shù)
intL=4;
//運算，刪除最高位數(shù)字
number=number-removeVal*R^(L-1);
//此時number=264

如果你能理解這兩個公式，那么 Rabin-Karp 算法就沒有任何難度，算法就是這樣，再高大上的技巧，都是在最簡單最基本的原理之上構(gòu)建的。不過在講 Rabin-Karp 算法之前，我們先來看一道簡單的力扣題目。

高效尋找重復子序列

看下力扣第 187 題「重復的 DNA 序列」，我簡單描述下題目：

DNA 序列由四種堿基A, G, C, T組成，現(xiàn)在給你輸入一個只包含A, G, C, T四種字符的字符串s代表一個 DNA 序列，請你在s中找出所有重復出現(xiàn)的長度為 10 的子字符串。

比如下面的測試用例：

輸入：s ="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出：["AAAAACCCCC","CCCCCAAAAA"]
解釋：子串"AAAAACCCCC"和"CCCCCAAAAA"都重復出現(xiàn)了兩次。

輸入：s ="AAAAAAAAAAAAA"
輸出：["AAAAAAAAAA"]

函數(shù)簽名如下：

ListfindRepeatedDnaSequences(Strings);

這道題的拍腦袋解法比較簡單粗暴，我直接窮舉所有長度為 10 的子串，然后借助哈希集合尋找那些重復的子串就行了，代碼如下：

//暴力解法
ListfindRepeatedDnaSequences(Strings){
intn=s.length();
//記錄出現(xiàn)過的子串
HashSetseen=newHashSet();
//記錄那些重復出現(xiàn)多次的子串
//注意要用哈希集合，防止記錄重復的結(jié)果
HashSetres=newHashSet<>();

for(inti=0;i+10<=?n;?i++)?{
????????String?subStr?=?s.substring(i,?i?+?10);
if(seen.contains(subStr)){
//之前出現(xiàn)過，找到一個重復的
res.add(subStr);
}else{
//之前沒出現(xiàn)過，加入集合
seen.add(subStr);
}
}
returnnewLinkedList<>(res);
}

這個算法肯定是沒問題的，只是時間復雜度略高。假設(shè)s的長度為N，目標子串的長度為L（本題L = 10），for 循環(huán)遍歷s的O(N)個字符，對每個字符都要截取長度為L的子字符串，所以這個算法的時間復雜是O(NL)。

遍歷整個s肯定是免不了的，問題是我們能不能不要每次都調(diào)用substring去截取子字符串？

你注意我們這個匹配過程實際上就是維護了一個長度為L = 10的定長窗口在從左向右滑動，是否可以借鑒前文滑動窗口算法框架中的做法，只維護left, right指針來劃定子字符串區(qū)間？

其實可以的，直接套用前文給出的滑動窗口算法框架寫出偽碼思路：

intL=10;
HashSetseen;

//滑動窗口代碼框架
CharWindowwindow;
intleft=0,right=0;
while(right//擴大窗口，移入字符
window.addRight(s[right]);
right++;

//當子串的長度達到要求
if(right-left==L){
//把窗口中的字符變成字符串，還是需要O(L)的時間
StringwindowStr=window.toString();
if(seen.contains(windowStr)){
print("找到一個重復子串:",windowStr);
}else{
seen.add(windowHash);
}

//縮小窗口，移出字符
window.removeLeft();
left++;
}
}

這段偽碼直接套用了滑動窗口算法框架，你應該不難理解。但你注意這個解法依然需要將窗口中的字符轉(zhuǎn)化成字符串然后去seen集合判斷是否存在重復，你一旦想把字符轉(zhuǎn)化成字符串，就難免需要O(L)的時間來操作。所以這個算法的時間復雜度還是沒有降低，依然是O(NL)。

所以優(yōu)化的關(guān)鍵在于，我們能不能不要真的把子字符串生成出來，而是用一些其他形式的唯一標識來表示滑動窗口中的子字符串，并且還能在窗口滑動的過程中快速更新？

有辦法的，回想一下本文開頭我們討論的那兩個公式，現(xiàn)在你應該明白的用意了。

你把AGCT四種字符等價為0123四個數(shù)字，那么長度為L = 10的一個堿基序列其實就可以等價為一個十位數(shù)，這個數(shù)字可以唯一標識一個子串。而且窗口移動的過程，其實就是給這個數(shù)字的最低位添加數(shù)字，并刪除最高位數(shù)字的過程，回顧之前的講解，添加和刪除數(shù)字的運算就是兩個公式，可以在O(1)的時間完成。

然后，我們不要在哈希集合中直接存儲子串了，而是存儲子串對應的十位數(shù)。因為一個十位數(shù)可以唯一標識一個子串，所以也可以起到識別重復的作用。

這樣，我們就避免了直接生成子串存入集合，而是生成一個十位數(shù)來表示子串，而且生成這個十位數(shù)的時間花費為O(1)，從而降低了匹配算法的時間復雜度。

其實你想下，你把一個字符串對象轉(zhuǎn)化成了一個數(shù)字，這是什么？這就是你設(shè)計的一個哈希算法，生成的數(shù)字就可以認為是字符串的哈希值。在滑動窗口中快速計算窗口中元素的哈希值，叫做滑動哈希技巧。

上述優(yōu)化思路的偽碼思路如下：

intL=10;
//集合中不要存儲字符串了，而是存儲字符串對應的哈希值
HashSetseen;

//滑動窗口代碼框架
CharWindowwindow;
intleft=0,right=0;
while(right//擴大窗口，移入字符
window.addRight(s[right]);
right++;

//當子串的長度達到要求
if(right-left==L){
//獲取當前窗口內(nèi)字符串的哈希值，時間O(1)
intwindowHash=window.hash();
//根據(jù)哈希值判斷是否曾經(jīng)出現(xiàn)過相同的子串
if(seen.contains(windowHash)){
//當前窗口中的子串是重復出現(xiàn)的
print("找到一個重復子串:",window.toString());
}else{
//當前窗口中的子串之前沒有出現(xiàn)過，記下來
seen.add(windowHash);
}

//縮小窗口，移出字符
window.removeLeft();
left++;
}
}

進一步，我們用一個 10 位數(shù)來標識一個長度為 10 的堿基字符序列，這需要 long 類型存儲，int 存不下 10 位數(shù)。但你注意這個 10 位數(shù)中所有的數(shù)字只會局限于0,1,2,3，是不是有些浪費？

換句話說，我們需要存儲的其實只是一個四進制下的十位數(shù)（共包含 4^10 個數(shù)字），卻用了十進制的十位數(shù)（可以包含 10^10 個數(shù)字）來保存，顯然是有些浪費的。

因為 4^10 = 1048576 < 10^8，所以只要我們在四進制的運算規(guī)則下進行運算，十進制的八位數(shù)就能存下，這樣的話 int 類型就夠用了，不需要 long 類型。

具體來說，只要改變我們之前那兩個公式的進制R就行了：

/*在最低位添加一個數(shù)字*/
//number的進制
intR=4;
//想在number的最低位添加的數(shù)字
intappendVal=0~3中的任意數(shù)字;
//運算，在最低位添加一位
number=R*number+appendVal;

/*在最高位刪除一個數(shù)字*/
//number的進制
intR=4;
//number最高位的數(shù)字
intremoveVal=0~3中的任意數(shù)字;
//此時number的位數(shù)
intL=?;
//運算，刪除最高位數(shù)字
number=number-removeVal*R^(L-1);

結(jié)合數(shù)字最高/最低位的處理技巧和滑動窗口代碼框架，我們就可以輕松地寫出最終的解法代碼：

ListfindRepeatedDnaSequences(Strings){
//先把字符串轉(zhuǎn)化成四進制的數(shù)字數(shù)組
int[]nums=newint[s.length()];
for(inti=0;iswitch(s.charAt(i)){
case'A':
nums[i]=0;
break;
case'G':
nums[i]=1;
break;
case'C':
nums[i]=2;
break;
case'T':
nums[i]=3;
break;
}
}
//記錄重復出現(xiàn)的哈希值
HashSetseen=newHashSet<>();
//記錄重復出現(xiàn)的字符串結(jié)果
HashSetres=newHashSet<>();

//數(shù)字位數(shù)
intL=10;
//進制
intR=4;
//存儲R^(L-1)的結(jié)果
intRL=(int)Math.pow(R,L-1);
//維護滑動窗口中字符串的哈希值
intwindowHash=0;

//滑動窗口代碼框架，時間O(N)
intleft=0,right=0;
while(right//擴大窗口，移入字符，并維護窗口哈希值（在最低位添加數(shù)字）
windowHash=R*windowHash+nums[right];
right++;

//當子串的長度達到要求
if(right-left==L){
//根據(jù)哈希值判斷是否曾經(jīng)出現(xiàn)過相同的子串
if(seen.contains(windowHash)){
//當前窗口中的子串是重復出現(xiàn)的
res.add(s.substring(left,right));
}else{
//當前窗口中的子串之前沒有出現(xiàn)過，記下來
seen.add(windowHash);
}
//縮小窗口，移出字符，并維護窗口哈希值（刪除最高位數(shù)字）
windowHash=windowHash-nums[left]*RL;
left++;
}
}
//轉(zhuǎn)化成題目要求的List類型
returnnewLinkedList<>(res);
}

滑動窗口算法本身的時間復雜度是O(N)，而窗口滑動的過程中的操作耗時都是O(1)（給res添加子串的過程不算），所以整體的時間復雜度是O(N)，這樣就把算法的復雜度降低到線性級別了。

Rabin-Karp 算法

有了上面由淺入深的鋪墊，你理解 Rabin-Karp 算法就非常容易了，因為上面這道題目的本質(zhì)就是一個字符串匹配的問題。

字符串匹配算法大家都很熟悉，讓你在文本串txt中搜索模式串pat的起始索引，暴力字符串匹配算法是這樣的：

//在文本串txt中搜索模式串pat的起始索引
intsearch(Stringtxt,Stringpat){
intN=txt.length(),L=pat.length();

for(inti=0;i+L<=?N;?i++)?{
????????String?subStr?=?txt.substring(i,?i?+?L);
????????if(subStr.equals(pat)){
//在txt中找到模式串pat，返回起始索引
returni;
}
}
//txt中不存在模式串pat
return-1;
}

你可以發(fā)現(xiàn)，這個邏輯和上面講的那道題的暴力解法非常類似，總的時間復雜度是O(LN)，優(yōu)化的核心也是子串subStr和模式串pat匹配的部分。

那么借鑒上面的思路，我們不要每次都去一個字符一個字符地比較子串和模式串，而是維護一個滑動窗口，運用滑動哈希算法一邊滑動一邊計算窗口中字符串的哈希值，拿這個哈希值去和模式串的哈希值比較，這樣就可以避免截取子串，從而把匹配算法降低為O(N)，這就是 Rabin-Karp 指紋字符串查找算法的核心邏輯。

那你可能會問，剛才我們處理的題目給你輸入的只有AGCT四種字符，所以可以轉(zhuǎn)化成數(shù)字，但面對五花八門的字符串，如何把他們轉(zhuǎn)化成數(shù)字計算哈希值呢？其實很簡單，字符本質(zhì)上就是編碼，而編碼其實就是數(shù)字。

比方說以 ASCII 碼為例，ASCII 碼其實就是 0~255 這 256 個數(shù)字，分別對應所有英文字符和英文符號。那么一個長度為L的 ASCII 字符串，我們就可以等價理解成一個L位的 256 進制的數(shù)字，這個數(shù)字就可以唯一標識這個字符串，也就可以作為哈希值。

有了這個想法，我們就可以直接復制粘貼上一道題的大部分代碼，寫出 Rabin-Karp 算法的主要邏輯：

//文本串
Stringtxt;
//模式串
Stringpat;


//需要尋找的子串長度為模式串pat的長度
intL=pat.length();
//僅處理ASCII碼字符串，可以理解為256進制的數(shù)字
intR=256;
//存儲R^(L-1)的結(jié)果
intRL=(int)Math.pow(R,L-1);
//維護滑動窗口中字符串的哈希值
intwindowHash=0;
//計算模式串的哈希值
longpatHash=0;
for(inti=0;i//滑動窗口代碼框架
intleft=0,right=0;
while(right//擴大窗口，移入字符（在最低位添加數(shù)字）
windowHash=R*windowHash+txt[right];
right++;

//當子串的長度達到要求
if(right-left==L){
//根據(jù)哈希值判斷窗口中的子串是否匹配模式串pat
if(patHash==windowHash){
//找到模式串
print("找到模式串，起始索引為",left);
returnleft;
}

//縮小窗口，移出字符（刪除最高位數(shù)字）
windowHash=windowHash-txt[left]*RL;
left++;
}
}
//沒有找到模式串
return-1;

相對上一道題的解法，這段代碼將進制數(shù)R改為了 256，同時計算了模式串pat的哈希值patHash用來和窗口中字符串的哈希值windowHash做對比，以便判斷是否找到了模式串，其他的代碼部分完全相同。

不過呢，這段代碼實際運行的時候會有一個嚴重的問題，那就是整型溢出。

你想，上一道題給定的 DNA 序列字符串只包含AGCT四種字符，所以我們可以把 DNA 序列抽象成四進制的數(shù)字，即算法中R = 4。相同位數(shù)下，四進制包含的數(shù)字數(shù)量是小于十進制包含的數(shù)字數(shù)量的。比方說L = 10時，4^10 = 1048576 < 10^8，即 10 位四進制數(shù)字用 8 位十進制數(shù)字就可以存下了。

但現(xiàn)在輸入為 ASCII 碼字符串，我們不得不把字符串抽象成 256 進制的數(shù)字，即算法中R = 256。而相同位數(shù)下，256 進制包含的數(shù)字數(shù)量顯然是遠大于十進制包含的數(shù)字數(shù)量的。比如L = 10時，256^10 = 1.2 x 10^24 < 10 ^25，所以你需要一個 25 位的十進制數(shù)才能表示一個 10 位的 256 進制數(shù)。

可想而知，如果你真的把字符串對應的 256 進制數(shù)字的十進制表示作為該字符串的哈希值，那恐怕L稍微大一點，像RL, windowHash, patHash這些變量就超級大了，long 類型都遠遠裝不下。

所以解決辦法是什么呢？如何把一個很大的數(shù)字映射到一個較小的范圍內(nèi)呢？答案是求模（余數(shù)）。

無論一個數(shù)字多大，你讓它除以Q，余數(shù)一定會落在[0, Q-1]的范圍內(nèi)。所以我們可以設(shè)置一個Q，用求模的方式讓windowHash和patHash保持在[0, Q-1]之間，就可以有效避免整型溢出。

具體來說，對于一個字符串，我們不需要把完整的 256 進制數(shù)字存下來，而是對這個巨大的 256 進制數(shù)求Q的余數(shù)，然后把這個余數(shù)作為該字符串的哈希值即可。

好，整型溢出的問題倒是解決了，但新的問題又來了：求模之后的哈希值不能和原始字符串一一對應了，可能出現(xiàn)一對多的情況，即哈希沖突。

比方說 10 % 7 等于 3，而 17 % 7 也等于 3，所以如果你得到余數(shù) 3，你能確定原始數(shù)字就一定是 10 么？不能。

類似的，如果你發(fā)現(xiàn)windowHash == patHash，你也不敢完全肯定窗口中的字符串一定就和模式串pat匹配，有可能它倆不匹配，但恰好求模算出來的哈希值一樣，這就產(chǎn)生了是「哈希沖突」。

在我的數(shù)據(jù)結(jié)構(gòu)精品課（文末「閱讀原文」查看詳情）中哈希表的章節(jié)中用拉鏈法和線性探查法解決了哈希表的哈希沖突。對于 Rabin-Karp 算法來說，當發(fā)現(xiàn)windowHash == patHash時，使用暴力匹配算法檢查一下窗口中的字符串和pat是否相同就可以避免哈希沖突了。因為希沖突出現(xiàn)的概率比較小，所以偶爾用一下暴力匹配算法是不影響總體的時間復雜度的。

明白了這些問題的解決方案，你就能很自然地寫出 Rabin-Karp 算法了：

//Rabin-Karp指紋字符串查找算法
intrabinKarp(Stringtxt,Stringpat){
//位數(shù)
intL=pat.length();
//進制（只考慮ASCII編碼）
intR=256;
//取一個比較大的素數(shù)作為求模的除數(shù)
longQ=1658598167;
//R^(L-1)的結(jié)果
longRL=1;
for(inti=1;i<=?L?-?1;i++){
//計算過程中不斷求模，避免溢出
RL=(RL*R)%Q;
}
//計算模式串的哈希值，時間O(L)
longpatHash=0;
for(inti=0;i//滑動窗口中子字符串的哈希值
longwindowHash=0;

//滑動窗口代碼框架，時間O(N)
intleft=0,right=0;
while(right//擴大窗口，移入字符
windowHash=((R*windowHash)%Q+txt.charAt(right))%Q;
right++;

//當子串的長度達到要求
if(right-left==L){
//根據(jù)哈希值判斷是否匹配模式串
if(windowHash==patHash){
//當前窗口中的子串哈希值等于模式串的哈希值
//還需進一步確認窗口子串是否真的和模式串相同，避免哈希沖突
if(pat.equals(txt.substring(left,right))){
returnleft;
}
}
//縮小窗口，移出字符
windowHash=(windowHash-(txt.charAt(left)*RL)%Q+Q)%Q;
//X%Q==(X+Q)%Q是一個模運算法則
//因為windowHash-(txt[left]*RL)%Q可能是負數(shù)
//所以額外再加一個Q，保證windowHash不會是負數(shù)

left++;
}
}
//沒有找到模式串
return-1;
}

有之前那么多鋪墊，算法邏輯應該沒啥可說的，就說一下模運算的兩個運算法則吧：

X%Q==(X+Q)%Q
(X+Y)%Q==(X%Q+Y%Q)%Q

稍微想一想就能理解這兩個運算法則，在代碼中但凡涉及到乘法和加法，都可能產(chǎn)生很大的結(jié)果，所以一有機會就可以運用上述法則對結(jié)果進行求模，以避免造成溢出。

Rabin-Karp 算法的時間復雜度是O(N + L)，N為文本串txt的長度，L為模式串pat的長度。當然，每次出現(xiàn)哈希沖突時會使用O(L)的時間進行暴力匹配，但考慮到只要Q設(shè)置的合理，哈希沖突的出現(xiàn)概率會很小，所以可以忽略不計。

最后說一下這個大素數(shù)Q的選擇。

為什么要這個Q盡可能大呢？主要是為了降低哈希沖突的概率。

因為代碼中你把這個Q作為除數(shù)，余數(shù)（哈希值）一定落在[0, Q-1]之間，所以Q越大，哈希值的空間就越大，就越不容易出現(xiàn)哈希沖突，整個算法的效率就會高一些。

為什么這個Q要是素數(shù)呢？依然是為了降低哈希沖突的概率。

舉個極端一點的例子，你令Q = 100，那么無論一個數(shù)X再大，X % Q的結(jié)果必然是X的最后兩位。換句話說X前面的那些位你根本沒利用，可想而知你這個哈希算法存在某些規(guī)律性，不夠隨機，進而更容易導致哈希沖突，降低算法的效率。

而如果你把Q設(shè)置為一個素數(shù)，可以更充分利用被除數(shù)X的每一位，得到的結(jié)果更隨機，哈希沖突的概率更小。這個結(jié)論是能夠在數(shù)學上證明的，有興趣的讀者可以自行搜索學習，我這里就不展開了。

最后總結(jié)一下吧，你看 Rabin-Karp 算法難嗎？其實就是滑動哈希配合滑動窗口，滑動哈希就是處理數(shù)字的一個小技巧，而滑動窗口算法是我們早就套路化的一個算法技巧。

所以，學習算法的關(guān)鍵并不是比誰刷題多，更不是死記硬背，而是要培養(yǎng)框架性的思維，抽象和化簡問題的能力，這也正是算法最有趣的地方，你學得越深入，越能體會到這種魅力。

審核編輯：湯梓紅