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

1、經(jīng)典算法之所以經(jīng)典，一定是因?yàn)橛歇?dú)特新穎的設(shè)計(jì)思想，那當(dāng)然要帶大家學(xué)習(xí)一波。

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

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

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

廢話不多說(shuō)了，直接上干貨。

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

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

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

為什么是乘以 10？因?yàn)槲覀兡J(rèn)探討的是十進(jìn)制數(shù)。這和我們操作二進(jìn)制數(shù)的時(shí)候是一個(gè)道理，左移一位就是把二進(jìn)制數(shù)乘以 2，右移一位就是除以 2。

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

這個(gè) 8000 是怎么來(lái)的？是 8 x 10^3 算出來(lái)的。8 是最高位的數(shù)字，10 是因?yàn)槲覀冞@里是十進(jìn)制數(shù)，3 是因?yàn)?8264 去掉最高位后還剩三位數(shù)。

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

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

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

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

高效尋找重復(fù)子序列

看下力扣第 187 題「重復(fù)的 DNA 序列」，我簡(jiǎn)單描述下題目：

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

比如下面的測(cè)試用例：

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

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

函數(shù)簽名如下：

ListfindRepeatedDnaSequences(Strings);

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

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

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

這個(gè)算法肯定是沒(méi)問(wèn)題的，只是時(shí)間復(fù)雜度略高。假設(shè)s的長(zhǎng)度為N，目標(biāo)子串的長(zhǎng)度為L（本題L = 10），for 循環(huán)遍歷s的O(N)個(gè)字符，對(duì)每個(gè)字符都要截取長(zhǎng)度為L的子字符串，所以這個(gè)算法的時(shí)間復(fù)雜是O(NL)。

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

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

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

intL=10;
HashSetseen;

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

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

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

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

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

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

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

然后，我們不要在哈希集合中直接存儲(chǔ)子串了，而是存儲(chǔ)子串對(duì)應(yīng)的十位數(shù)。因?yàn)橐粋€(gè)十位數(shù)可以唯一標(biāo)識(shí)一個(gè)子串，所以也可以起到識(shí)別重復(fù)的作用。

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

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

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

intL=10;
//集合中不要存儲(chǔ)字符串了，而是存儲(chǔ)字符串對(duì)應(yīng)的哈希值
HashSetseen;

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

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

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

進(jìn)一步，我們用一個(gè) 10 位數(shù)來(lái)標(biāo)識(shí)一個(gè)長(zhǎng)度為 10 的堿基字符序列，這需要 long 類型存儲(chǔ)，int 存不下 10 位數(shù)。但你注意這個(gè) 10 位數(shù)中所有的數(shù)字只會(huì)局限于0,1,2,3，是不是有些浪費(fèi)？

換句話說(shuō)，我們需要存儲(chǔ)的其實(shí)只是一個(gè)四進(jìn)制下的十位數(shù)（共包含 4^10 個(gè)數(shù)字），卻用了十進(jìn)制的十位數(shù)（可以包含 10^10 個(gè)數(shù)字）來(lái)保存，顯然是有些浪費(fèi)的。

因?yàn)?4^10 = 1048576 < 10^8，所以只要我們?cè)谒倪M(jìn)制的運(yùn)算規(guī)則下進(jìn)行運(yùn)算，十進(jìn)制的八位數(shù)就能存下，這樣的話 int 類型就夠用了，不需要 long 類型。

具體來(lái)說(shuō)，只要改變我們之前那兩個(gè)公式的進(jìn)制R就行了：

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

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

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

ListfindRepeatedDnaSequences(Strings){
//先把字符串轉(zhuǎn)化成四進(jìn)制的數(shù)字?jǐn)?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;
}
}
//記錄重復(fù)出現(xiàn)的哈希值
HashSetseen=newHashSet<>();
//記錄重復(fù)出現(xiàn)的字符串結(jié)果
HashSetres=newHashSet<>();

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

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

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

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

Rabin-Karp 算法

有了上面由淺入深的鋪墊，你理解 Rabin-Karp 算法就非常容易了，因?yàn)樯厦孢@道題目的本質(zhì)就是一個(gè)字符串匹配的問(wèn)題。

字符串匹配算法大家都很熟悉，讓你在文本串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)，這個(gè)邏輯和上面講的那道題的暴力解法非常類似，總的時(shí)間復(fù)雜度是O(LN)，優(yōu)化的核心也是子串subStr和模式串pat匹配的部分。

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

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

比方說(shuō)以 ASCII 碼為例，ASCII 碼其實(shí)就是 0~255 這 256 個(gè)數(shù)字，分別對(duì)應(yīng)所有英文字符和英文符號(hào)。那么一個(gè)長(zhǎng)度為L的 ASCII 字符串，我們就可以等價(jià)理解成一個(gè)L位的 256 進(jìn)制的數(shù)字，這個(gè)數(shù)字就可以唯一標(biāo)識(shí)這個(gè)字符串，也就可以作為哈希值。

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

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


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

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

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

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

不過(guò)呢，這段代碼實(shí)際運(yùn)行的時(shí)候會(huì)有一個(gè)嚴(yán)重的問(wèn)題，那就是整型溢出。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

left++;
}
}
//沒(méi)有找到模式串
return-1;
}

有之前那么多鋪墊，算法邏輯應(yīng)該沒(méi)啥可說(shuō)的，就說(shuō)一下模運(yùn)算的兩個(gè)運(yùn)算法則吧：

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

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

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

最后說(shuō)一下這個(gè)大素?cái)?shù)Q的選擇。

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

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

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

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

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

最后總結(jié)一下吧，你看 Rabin-Karp 算法難嗎？其實(shí)就是滑動(dòng)哈希配合滑動(dòng)窗口，滑動(dòng)哈希就是處理數(shù)字的一個(gè)小技巧，而滑動(dòng)窗口算法是我們?cè)缇吞茁坊囊粋€(gè)算法技巧。

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

審核編輯：湯梓紅