————— 第二天 —————
什么意思呢？讓我們來舉一個(gè)例子：
在上圖中，字符串B是A的子串，B第一次在A中出現(xiàn)的位置下標(biāo)是2（字符串的首位下標(biāo)是0），所以返回 2。
我們?cè)倏戳硪粋€(gè)例子：
在上圖中，字符串B在A中并不存在，所以返回 -1。
為了統(tǒng)一概念，在后文中，我們把字符串A稱為主串，把字符串B稱為模式串。
小灰的想法簡(jiǎn)單粗暴，讓我們用下面的例子來演示一下：
第一輪，我們從主串的首位開始，把主串和模式串的字符逐個(gè)比較：
顯然，主串的首位字符是a，模式串的首位字符是b，兩者并不匹配。
第二輪，我們把模式串后移一位，從主串的第二位開始，把主串和模式串的字符逐個(gè)比較：
主串的第二位字符是b，模式串的第二位字符也是b，兩者匹配，繼續(xù)比較：
主串的第三位字符是b，模式串的第三位字符也是c，兩者并不匹配。
第三輪，我們把模式串再次后移一位，從主串的第三位開始，把主串和模式串的字符逐個(gè)比較：
主串的第三位字符是b，模式串的第三位字符也是b，兩者匹配，繼續(xù)比較：
主串的第四位字符是c，模式串的第四位字符也是c，兩者匹配，繼續(xù)比較：
主串的第五位字符是e，模式串的第五位字符也是e，兩者匹配，比較完成！
由此得到結(jié)果，模式串 bce 是主串 abbcefgh 的子串，在主串第一次出現(xiàn)的位置下標(biāo)是 2：
以上就是小灰想出的解決方案，這個(gè)算法有一個(gè)名字，叫做BF算法，是Brute Force（暴力算法）的縮寫。
上圖的情況，在每一輪進(jìn)行字符匹配時(shí)，模式串的前三個(gè)字符a都和主串中的字符相匹配，一直檢查到模式串最后一個(gè)字符b，才發(fā)現(xiàn)不匹配：
這樣一來，兩個(gè)字符串在每一輪都需要白白比較4次，顯然非常浪費(fèi)。
假設(shè)主串的長度是m，模式串的長度是n，那么在這種極端情況下，BF算法的最壞時(shí)間復(fù)雜度是O（mn）。
————————————
比較哈希值是什么意思呢？
用過哈希表的朋友們都知道，每一個(gè)字符串都可以通過某種哈希算法，轉(zhuǎn)換成一個(gè)整型數(shù)，這個(gè)整型數(shù)就是hashcode：
hashcode = hash（string）
顯然，相對(duì)于逐個(gè)字符比較兩個(gè)字符串，僅比較兩個(gè)字符串的hashcode要容易得多。
給定主串和模式串如下（假定字符串只包含26個(gè)小寫字母）：
第一步，我們需要生成模式串的hashcode。
生成hashcode的算法多種多樣，比如：
按位相加
這是最簡(jiǎn)單的方法，我們可以把a(bǔ)當(dāng)做1，b當(dāng)做2，c當(dāng)做3......然后把字符串的所有字符相加，相加結(jié)果就是它的hashcode。
bce = 2 + 3 + 5 = 10
但是，這個(gè)算法雖然簡(jiǎn)單，卻很可能產(chǎn)生hash沖突，比如bce、bec、cbe的hashcode是一樣的。
轉(zhuǎn)換成26進(jìn)制數(shù)
既然字符串只包含26個(gè)小寫字母，那么我們可以把每一個(gè)字符串當(dāng)成一個(gè)26進(jìn)制數(shù)來計(jì)算。
bce = 2*(26^2) + 3*26 + 5 = 1435
這樣做的好處是大幅減少了hash沖突，缺點(diǎn)是計(jì)算量較大，而且有可能出現(xiàn)超出整型范圍的情況，需要對(duì)計(jì)算結(jié)果進(jìn)行取模。
為了方便演示，后續(xù)我們采用的是按位相加的hash算法，所以bce的hashcode是10：
第二步，生成主串當(dāng)中第一個(gè)等長子串的hashcode。
由于主串通常要長于模式串，把整個(gè)主串轉(zhuǎn)化成hashcode是沒有意義的，只有比較主串當(dāng)中和模式串等長的子串才有意義。
因此，我們首先生成主串中第一個(gè)和模式串等長的子串hashcode，
即abb = 1 + 2 + 2 = 5：
第三步，比較兩個(gè)hashcode。
顯然，5！=10，說明模式串和第一個(gè)子串不匹配，我們繼續(xù)下一輪比較。
第四步，生成主串當(dāng)中第二個(gè)等長子串的hashcode。
bbc = 2 + 2 + 3 = 7：
第五步，比較兩個(gè)hashcode。
顯然，7！=10，說明模式串和第二個(gè)子串不匹配，我們繼續(xù)下一輪比較。
第六步，生成主串當(dāng)中第三個(gè)等長子串的hashcode。
bce= 2 + 3 + 5 = 10：
第七步，比較兩個(gè)hashcode。
顯然，10 ==10，兩個(gè)hash值相等！這是否說明兩個(gè)字符串也相等呢？
別高興的太早，由于存在hash沖突的可能，我們還需要進(jìn)一步驗(yàn)證。
第八步，逐個(gè)字符比較兩字符串。
hashcode的比較只是初步驗(yàn)證，之后我們還需要像BF算法那樣，對(duì)兩個(gè)字符串逐個(gè)字符比較，最終判斷出兩個(gè)字符串匹配。
最后得出結(jié)論，模式串bce是主串a(chǎn)bbcefgh的子串，第一次出現(xiàn)的下標(biāo)是2。
什么意思呢？讓我們?cè)賮砜匆粋€(gè)例子：
上圖中，我已知子串a(chǎn)bbcefg的hashcode是26，那么如何計(jì)算下一個(gè)子串，也就是bbcefgd的hashcode呢？
我們沒有必要把子串的字符重新進(jìn)行累加運(yùn)算，而是可以采用一個(gè)更簡(jiǎn)單的方法。由于新子串的前面少了一個(gè)a，后面多了一個(gè)d，所以：
新hashcode = 舊hashcode - 1 + 4 = 26-1+4 = 29
再下一個(gè)子串bcefgde的計(jì)算也是同理：
新hashcode = 舊hashcode - 2 + 5 = 29-2+5 = 32
public static int rabinKarp(String str, String pattern){
//主串長度
int m = str.length;
//模式串的長度
int n = pattern.length;
//計(jì)算模式串的hash值
int patternCode = hash(pattern);
//計(jì)算主串當(dāng)中第一個(gè)和模式串等長的子串hash值
int strCode = hash(str.substring(0, n));
//用模式串的hash值和主串的局部hash值比較。
//如果匹配，則進(jìn)行精確比較；如果不匹配，計(jì)算主串中相鄰子串的hash值。
for (int i=0; i<m-n+1; i++) {
if(strCode == patternCode && compareString(i, str, pattern)){
return i;
}
//如果不是最后一輪，更新主串從i到i+n的hash值
if(i<m-n){
strCode = nextHash(str, strCode, i, n);
}
}
return -1;
}
private static int hash(String str){
int hashcode = 0;
//這里采用最簡(jiǎn)單的hashcode計(jì)算方式：
//把a(bǔ)當(dāng)做1，把b當(dāng)中2，把c當(dāng)中3.....然后按位相加
for(int i = 0; i < str.length; i++) {
hashcode += str.charAt(i)-'a';
}
return hashcode;
}
private static
int nextHash(String str, int hash, int index, int n){
hash -= str.charAt(index)-'a';
hash += str.charAt(index+n)-'a';
return hash;
}
private static boolean compareString(int i, String str, String pattern)
{
String strSub = str.substring(i, i+pattern.length);
return strSub.equals(pattern);
}
public static void main(String[] args)
{
String str = "aacdesadsdfer";
String pattern = "adsd";
System.out.println("第一次出現(xiàn)的位置:" + rabinKarp(str, pattern));
}
本文為程序員小灰（ID：chengxuyuanxiaohui）投稿。
