https://www.cnblogs.com/ljc20020730/p/7285694.html
字符串x1,x2,x3……xk
基底e;模數(shù)mo;
hash=(xke^0+xk-1e1+......+x1*ek-1)mod mo
注意：
①字符映射到數(shù)字不要映射到0
②基底e>字符種類數(shù)
③據(jù)說mo數(shù)為大素數(shù)出錯概率小
mo=1000000007（存int64）
mo=666623333
遞推建hash：
初始條件：hash[1]=x1;
遞推式：hash[i]=(hash[i-1]*e+xi)mod mo;
區(qū)間hash：
對于任意關(guān)于x的子串xi-xj
hash[i,j]=(xje^0+xj+1e1+......+xi*ej-i)mod mo;
O(n)的算法
hash[i,j]=(hash[j]-hash[i-1]*e^(j-i+1) mod mo+mo)mod mo
O(1)的算法
代碼如下：
https://github.com/TheAlgorithms/Python/blob/master/strings/rabin_karp.py
# Numbers of alphabet which we call base
alphabet_size = 256
# Modulus to hash a string
modulus = 1000003
def rabin_karp(pattern, text):
"""
The Rabin-Karp Algorithm for finding a pattern within a piece of text
with complexity O(nm), most efficient when it is used with multiple patterns
as it is able to check if any of a set of patterns match a section of text in o(1) given the precomputed hashes.
This will be the simple version which only assumes one pattern is being searched for but it's not hard to modify
1) Calculate pattern hash
2) Step through the text one character at a time passing a window with the same length as the pattern
calculating the hash of the text within the window compare it with the hash of the pattern. Only testing
equality if the hashes match
"""
p_len = len(pattern)
t_len = len(text)
if p_len > t_len:
return False
p_hash = 0
text_hash = 0
modulus_power = 1
# Calculating the hash of pattern and substring of text
for i in range(p_len):
#計算patten字符串和文本的第一個pattern長度的字符串的 hash
#其他帖子里說的預(yù)處理部分彬碱， 耗時O(m)的部分
p_hash = (ord(pattern[i]) + p_hash * alphabet_size) % modulus
text_hash = (ord(text[i]) + text_hash * alphabet_size) % modulus
if i == p_len - 1:
continue
modulus_power = (modulus_power * alphabet_size) % modulus
for i in range(0, t_len - p_len + 1):
if text_hash == p_hash and text[i : i + p_len] == pattern:
return True
if i == t_len - p_len:
continue
# Calculating the ruling hash
#這里使用到了O(1)計算的過程巷疼，用之前窗口的hash值減去字符串第一個字符貢獻的hash之部分，再加上新的一位字符的hash值搬泥。
text_hash = (
(text_hash - ord(text[i]) * modulus_power) * alphabet_size
+ ord(text[i + p_len])
) % modulus
return False
def test_rabin_karp():
"""
>>> test_rabin_karp()
Success.
"""
# Test 1)
pattern = "abc1abc12"
text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
text2 = "alskfjaldsk23adsfabcabc"
assert rabin_karp(pattern, text1) and not rabin_karp(pattern, text2)
# Test 2)
pattern = "ABABX"
text = "ABABZABABYABABX"
assert rabin_karp(pattern, text)
# Test 3)
pattern = "AAAB"
text = "ABAAAAAB"
assert rabin_karp(pattern, text)
# Test 4)
pattern = "abcdabcy"
text = "abcxabcdabxabcdabcdabcy"
assert rabin_karp(pattern, text)
# Test 5)
pattern = "Lü"
text = "Lüsai"
assert rabin_karp(pattern, text)
pattern = "Lue"
assert not rabin_karp(pattern, text)
print("Success.")
if __name__ == "__main__":
test_rabin_karp()
網(wǎng)上的帖子有很多伏尼，大致看完之后爆阶，本人傾向于下面帖子的分析：
https://blog.csdn.net/lucylove3943/article/details/83491416
Rabin-Karp是用來解決字符串匹配（查重）的問題的。該問題的嚴謹定義如下：
Input：一段字符串t柬讨，和一個字符串p
Output：如果t中含有p，那么輸出yes，如果沒有鱼的，輸出no
看p是不是t的子字符串，如果是的話猿规，輸出yes宙橱，如果不是的話，輸出no环葵。
Michael O. Rabin和Richard M. Karp在1987年提出一個想法宝冕，即可以對模式串進行哈希運算并將其哈希值與文本中子串的哈希值進行比對猬仁∠扔總的來說這一想法非常淺顯的烁，唯一的問題在于我們需要找到一個哈希函數(shù) ，它需要能夠?qū)Σ煌淖址祷夭煌墓Ｖ盗迓＠缃罄祝摴：瘮?shù)可能會對每個字符的ASCII碼進行算，
如何hashing字符串
比較籠統(tǒng)和寬泛的來說咧虎，哈希其實就是把一個定義域較寬的集合映射到一個值域較小的集合计呈。一般來說，我們映射的結(jié)果是一個整數(shù)茁彭，也就是俗稱的地址扶歪。比如說現(xiàn)在有一個數(shù)為x，我們希望進行哈希運算之后的H(x)是一個整數(shù)妹萨，然后我們把x放到哈希表中地址為H(x)的地方媳禁。
如果x是一個數(shù)字竣稽，這個理解起來比較直觀霍弹，我們可以定義哈希函數(shù)為對這個數(shù)字的四則運算，得到一個新的數(shù)字岛宦，作為x的哈希值耍缴。
那么如果x是一個字符串S呢挽霉？如果通過一個哈希函數(shù)变汪，把字符串S轉(zhuǎn)換為一個整數(shù)呢裙盾？Hashing字符串一般用的是如下公式：
其中，代表的是S的定義域大小庐完，比如說如果S全是英文字母徘熔，那么的值為26，因為英文字母就只有26個生音。然后這個函數(shù)是一個映射函數(shù)窒升，映射S的定義域中的每一個字符到數(shù)字的函數(shù)。
根據(jù)上面的這個公式域醇，就能把任意一個字符串S映射為一個整數(shù)蓉媳。
Brute Force算法（暴力解法）
暴力破解Substring Pattern Matching的方法十分直觀酪呻，過程如下：
假設(shè)字符串t的長度為n，字符串p的長度為m漆腌。
在字符串t上阶冈，放一個長度為m窗口window。
從頭開始慢慢的滑動這個窗口window填具，每滑動一次匆骗，就把窗口里的內(nèi)容和p對比一下誉简。
如果一樣闷串，就返回yes衡蚂。如果不一樣，那么繼續(xù)往右滑動一格窗口window年叮。
從上述算法可知玻募，in worst case，一共會有(n-m+1)個窗口滑動跃惫。->這一步的復(fù)雜度是O(n)
然后每次窗口滑動艾栋，都涉及到兩個長度為m的字符串的比較。->這一步的復(fù)雜度是O(m)
由于這兩部是一個nested loop先较，所以最終的算法復(fù)雜度是O(m*n)悼粮。
Rabin-Karp算法
基本思想和暴力破解算法是一樣的扣猫。也需要一個大小為m的窗口，但是不一樣的是申尤，不是直接比較兩個長度為m的字符串瀑凝，而是比較他們的哈希值。
同樣的，現(xiàn)在我們做他們的復(fù)雜度分析渴杆，in worst case，一共會有(n-m+1)個窗口滑動某筐。->這一步的復(fù)雜度是O(n)
這個是不變的冠跷，但是由于哈希值都是數(shù)字，所以兩個數(shù)字的比較抄囚，只需要O(1)橄务。
但是計算哈希值的時間呢？
在一開始的時候重挑，我們需要計算p的哈希值棠涮，由于p的長度為m严肪，所以計算p的哈希值的時間為O(m).
然后每一次移動窗口，都需要對窗口內(nèi)的字符串計算哈希值劲室，此時這個字符串的長度為m结窘，所以計算它哈希值的時間也為O(m).如果照這樣看，算法復(fù)雜度還是O(m+n)喉磁，和上面的暴力破解算法沒有任何區(qū)別官脓。
但是實際上卑笨，計算移動窗口內(nèi)的哈希值并不需要O(m)，在已知前一個窗口的哈希值的情況下妖滔，計算當(dāng)前窗口的哈希值，只需要O(1)的時間復(fù)雜度座舍。
現(xiàn)在再來看上面提到的計算字符串哈希值的函數(shù)曲秉，假設(shè)現(xiàn)在窗口的起點在j這個位置，此時窗口內(nèi)的字符串哈希值為：
那么榆鼠，當(dāng)計算下一個窗口的哈希值時璧眠，也就是當(dāng)窗口的起點為j+1時读虏，哈希函數(shù)值可由如下方法計算：
所以盖桥，這樣看來，在計算出第一個窗口的函數(shù)值之后腰鬼，后面的每一個窗口哈希值都可以根據(jù)上述公式計算塑荒，只需要做一次減法，一次乘法彼硫，一次加法凌箕。所以之后的每一次哈希值計算都是O(1)的復(fù)雜度牵舱。
那么重頭來算一次復(fù)雜度：
一共有(n-m+1)個窗口，復(fù)雜度為O(n).
計算p的哈希值O(m)礁凡，計算第一個窗口的復(fù)雜度，O(m).
此后計算每一個窗口的復(fù)雜度O(1).
所以最終的復(fù)雜度是O(m+n)纫溃。
參考資料：
https://blog.csdn.net/woshinannan741/article/details/50372598
https://blog.csdn.net/lucylove3943/article/details/83491416
https://blog.csdn.net/m0_37846371/article/details/72854890
https://blog.csdn.net/tyler_download/article/details/52457108
自己的總結(jié)：
對字符進行編碼韧掩，不同的字符對應(yīng)不同的整數(shù)數(shù)值疗锐，選取一個基數(shù)N（類似16進制的16）费彼，基數(shù)>字符種類數(shù)箍铲，類比于16進制數(shù)一樣，每個字符對應(yīng)一個N進制數(shù)颠猴，且各不相同翘瓮，然后將長度為M的pattern字符串看作一個M位的N進制數(shù)，Hash函數(shù)就是計算這個M位N進制數(shù)的 數(shù)值调榄。那么不同的pattern字符串一定是對應(yīng)不同的數(shù)值
然后對長度位K的文本呵扛，從位置0開始今穿，每次滑動1個位置，計算K-M+1次窗口大小為M的字符串的hash值凤价，與pattern的hash值做比對即可拔创。
為什么有概率比對不上？
做個極限假設(shè)慢逾，假如N很大侣滩，M也較大（匹配字符串較長），那么pattern的hash值-P0和每次滑動比對窗口的M位字符串對應(yīng)的hash-P1就有可能是一個很大的數(shù)值寝志，大到int或者longint 32bit/64bit數(shù)值表示不了（會溢出）策添，假設(shè)int型表示hash值，那么就會出現(xiàn)P1 = P0 + K*2^32 (K為整數(shù))的情況乐导，即P0-P1 同余的情況（這里模數(shù)相當(dāng)于是2^32）物臂，所以模數(shù)mo選擇越大产上，出錯概率越小，并不是什么玄學(xué)泽本，因為溢出的概率越小姻僧。
