Rabin-Karp字符串匹配算法是對每一個字符進行比較，把每個字符進行對應進制數(shù)并取模運算，然后比較每個字符的函數(shù)值。預處理時間是O(m)，匹配時間是O((n-m+1)m)。
Rabin-Karp算法的思想：
1 假設(shè)目標字符串長度為N，待匹配字符串的長度為M （M<=N）
2 首先計算待匹配字符串的hash值，然后計算目標字符串前M個字符的hash值
3 比較前面計算的2個hash值，比較次數(shù)N-M+1
? - 若hash值不相等，則繼續(xù)計算目標字符串的下一個長度為M的字符子串的hash值
? - 若hash值相同，則需要使用樸素算法再次判斷是否為相同的字符串。
這里有一段關(guān)于Rabin-Karp算法的分析：
Rabin-Karp算法相對于樸素字符串匹配算法比較快的原因有2點：
① Rabin-Karp算法是將字符串計算成了數(shù)值，數(shù)值的比較 相比于對字符串的包含的字符進行逐個比較（樸素字符串匹配算法）會更快。
② 樸素字符串匹配每一次都是2個字符串的重新匹配，之前的字符串的匹配結(jié)果不能應用到這次匹配中。而Rabin-Karp可以利用上次匹配的結(jié)果信息： 字符串生成的數(shù)值可以表示出字符的前后順序，而且可以隨時去掉某個字符的值，可以隨時添加一個新字符的值。當一次匹配結(jié)束后，去掉源串第一個字符的的值，再加上這次比較來自于源串中要新加的字符串的值。
Rabin-Karp算法舉例：
比如我們要在源串 "9876543210520" 中查找 "520"，因為這些字符串中只有數(shù)字，所以我們可以使用字符集 {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'} 來表示字符串中的所有元素，并且將各個字符映射到數(shù)字 0～9，然后用 M 表示字符集中字符的總個數(shù)，這里是 10，那么我們就可以將搜索詞 "520" 轉(zhuǎn)化為下面的數(shù)值：
("5"的映射值 * M + "2"的映射值) * M + "0"的映射值 = (5 * 10 + 2) * 10 + 0 = 520
“搜索詞”計算好了，那么接下來計算“源串”，取“源串”的前 n 個字符（n 為“搜索詞”的長度）"987"，按照同樣的方法計算其數(shù)值：
("9"的映射值 * M + "8"的映射值) * M + "7"的映射值 = (9 * 10 + 8) * 10 + 7 = 987
然后將該值與搜索詞的值進行比較即可。比較發(fā)現(xiàn) 520 與 987 不相等，則說明 "520" 與 "987" 不匹配，則繼續(xù)向下尋找，這時候該如何做呢？下一步應該比較 "520" 跟 "876" 了，那么我們?nèi)绾卫们耙徊降男畔⒛?？首先我們?987 減去代表字符 "9" 的部分：
987 - ("9"的映射值 * (M 的 n - 1 次方)) = 987 - (9 * (10 的 2 次方)) = 987 - 900 = 87
然后再乘以 M（這里是 10），再加上 "6" 的映射值，不就成了 876 了么：
87 * M + "6"的映射值 = 87 * 10 + 6 = 876<br/>
再進行比較。
參考文檔：
http://www.cnblogs.com/golove/p/3234673.html
https://github.com/gopher-learning/night-reading-go/blob/master/20180510/README.md
https://blog.csdn.net/chenhanzhun/article/details/39895077
https://github.com/gopher-learning/night-reading-go/blob/master/20180510/README.md
