<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Rabin Karp - Rabin-Karp算法 -------- #### 問題 在文本$$ text $$中查找字符串$$ pattern $$出現的所有位置（$$ text $$長度為$$ n $$，$$ pattern $$長度為$$ m $$，$$ n, m $$都是正整數且$$ n \gt m $$）。 #### 解法 從位置$$ i, j $$開始的匹配，每次成功的匹配都需要時間復雜度為$$ O(m) $$的遍歷，才能確定$$ text[i \dots i+m-1] = pattern[0 \dots m-1] = pattern $$是否成立。如果用$$ hash(i, i+m-1) $$來表示字符串$$ text[i \dots i+m-1] $$的哈希值，$$ hash(pattern) $$表示字符串$$ pattern $$的哈希值，則比較$$ hash(i, i+m-1) = hash(pattern) $$是否成功的時間復雜度為$$ O(1) $$。顯然當$$ hash(i, i+m-1) \ne hash(pattern) $$時必然有$$ text[i \dots i+m-1] \ne pattern $$。反之若哈希值相同，再用簡單匹配來確定字符串$$ text[i \dots i+m-1] = pattern $$確實為真，這樣即可找出所有成功匹配。 我們通過Rabin Fingerprint算法計算字符串的哈希值，ASCII碼中每個字符對應的數字值范圍在$$ [0 - 127] $$之間，設每讀入新的字符時舊的哈希值的擴大倍數為$$ base = 128 $$（這個$$ base $$是字符表大小的范圍）。則有： $$ hash(0, i+1) = hash(0, i) \cdot base + text[i+1] $$ 實際我們想計算的是$$ hash(text[i \dots i+m-1]) $$，當$$ i $$右移一位時，不僅要考慮右邊界新加入的字符，還需要考慮左邊界離開的字符。一個字符從最右邊界一直移動到最左邊界，其值乘以$$ base $$共$$ m-1 $$次。因此哈希值要減去$$ base^{m-1} \cdot text[i] $$。特別注意$$ pattern $$長度為$$ 1 $$時$$ base^{m-1} = 1 $$： $$ hash(i+1, i+m) = hash(i, i+m-1) \cdot base - base^{m-1} \cdot text[i] + text[i+1] $$ 由于數字太大時計算會溢出，用一個較大的素數來對結果取模$$ prime = 16777619 $$，最終得到哈希函數： $$ hash(i+1, i+m]) = (hash(i, i+m-1) \cdot base - base^{m-1} \cdot text[i] + text[i+1]) % prime $$ Rabin Fingerprint算法可以連續的處理字符串，在時間復雜度為$$ O(n) $$內求出所有字符串$$ text[i \dots i+m-1] $$的哈希值（其中$$ 0 \ge i \ge n-m+1 $$）。Rabin-Karp算法的時間復雜度為$$ O(n + z \cdot m) $$，其中$$ z $$是模式$$ pattern $$在文本中出現的次數。 -------- Rabin-Karp * http://www.cs.cmu.edu/afs/cs/academic/class/15451-f14/www/lectures/lec6/karp-rabin-09-15-14.pdf * https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/ Rabin Fingerprint * http://www.xmailserver.org/rabin.pdf * https://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf -------- #### 源碼 [RabinKarp.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/RabinKarp.h) [RabinKarp.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/RabinKarp.cpp) #### 測試 [RabinKarpTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/RabinKarpTest.cpp)