字符串匹配RabinKarp算法讲解

问题描述&＃xff1a;

      Rabin-Karp的预处理时间是O(m)&＃xff0c;匹配时间O( ( n - m &＃43; 1 ) m )既然与朴素算法的匹配时间一样&＃xff0c;而且还多了一些预处理时间&＃xff0c;那为什么我们还要学习这个算法呢&＃xff1f;虽然Rain-Karp在最坏的情况下与朴素匹配一样&＃xff0c;但是实际应用中往往比朴素算法快很多。而且该算法的期望匹配时间是O(n)【参照《算法导论》】&＃xff0c;但是Rabin-Karp算法需要进行数值运算&＃xff0c;速度必然不会比KMP算法快&＃xff0c;那我们有了KMP算法以后为什么还要学习Rabin-Karp算法呢&＃xff1f;个人认为学习的是一种思想&＃xff0c;一种解题的思路&＃xff0c;当我们见识的越多&＃xff0c;眼界也就也开阔&＃xff0c;面对实际问题的时候&＃xff0c;就能找到更加合适的算法。比如二维模式匹配&＃xff0c;Rabin-Karp就是一种好的选择。

      而且Rabin-Karp算法非常有趣&＃xff0c;将字符当作数字来处理&＃xff0c;基本思路&＃xff1a;如果Tm是一个长度为 |P| 的T的子串&＃xff0c;且转换为数值后模上一个数&＃xff08;一般为素数&＃xff09;与模式字符串P转换成数值后模上同一个数的值相同&＃xff0c;则Tm可能是一个合法的匹配。

We can compute p in time O(m) using Horner&＃39;s rule (see Section 32.1):

p &＃61; P[m] &＃43; 10 (P[m - 1] &＃43; 10(P[m - 2] &＃43; . . . &＃43; 10(P[2] &＃43; 10P[1]) . . . )).
The value t0 can be similarly computed from T[1 . . m] in time O(m).To compute the remaining values t1, t2, . . . , tn-m in time O(n - m), it suffices to observe that ts &＃43; 1 can be computed from ts in constant time, sincets &＃43; 1 &＃61; 10(ts - 10m - 1T[s &＃43; 1]) &＃43; T[s &＃43; m &＃43; 1].(34.1)
For example, if m&＃61; 5 and ts &＃61; 31415, then we wish to remove the high-order digit T[s &＃43; 1] &＃61; 3 and bring in the new low-order digit (suppose it is T[s &＃43; 5 &＃43; 1] &＃61; 2) to obtaints&＃43;1 &＃61; 10(31415 - 10000.3) &＃43; 2&＃61; 14152 .

http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap34.htm

以上算法很简单&＃xff0c;但是当模式字符串P的长度达到7以后就要出错了&＃xff0c;即使将t&＃xff0c;p定义为long unsigned int型也解决不了大问题&＃xff0c;也就是说上面代码没什么用。

　　其中b是基数&＃xff0c;相当于把字符串看作b进制数。这样&＃xff0c;字符串S&＃61;s1s2s3...sn从位置k&＃43;1开始长度为m的字符串子串S[k&＃43;1...k&＃43;m]的哈希值&＃xff0c;就可以利用从位置k开始的字符串子串S[k...k&＃43;m-1]的哈希值&＃xff0c;直接进行如下计算&＃xff1a;H(S[k&＃43;1...k&＃43;m])&＃61;&＃xff08;H(S[k...k&＃43;m-1]&＃xff09;* b - sk*b^m &＃43; s(k&＃43;m)&＃xff09; mod h

    该算法的难点就在于p和t的值可能很大&＃xff0c;导致不能方便的对其进行处理。对这个问题有一个简单的补救办法&＃xff0c;用一个合适的数q来计算p和t的模。每个字符其实十一个十进制的整数&＃xff0c;所以p&＃xff0c;t以及递归式都可以对模q进行&＃xff0c;所以可以在O(m)的时间里计算出模q的p值&＃xff0c;在O&＃xff08;n - m &＃43; 1&＃xff09;时间内计算出模q的所有t值。参见《算法导论》或http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap34.htm

递推式是如下这个式子&＃xff1a; 

ts&＃43;1 &＃61; (d *( ts-T[s &＃43; 1]*h) &＃43; T[s &＃43; m &＃43; 1 ] ) mod q

例如&＃xff0c;如果d &＃61; 10 &＃xff08;十进制&＃xff09;m&＃61; 5, ts &＃61; 31415,我们希望去掉最高位数字T[s &＃43; 1] &＃61; 3,再加入一个低位数字&＃xff08;假定 T[s&＃43;5&＃43;1] &＃61; 2)就得到&＃xff1a;

ts&＃43;1 &＃61; 10*(31415 - 1000*3) &＃43;2 &＃61; 14152

于是&＃xff0c;只要不断这样计算开始位置右移一位后的字符串子串的哈希值&＃xff0c;就可以在O&＃xff08;n&＃xff09;时间内得到所有位置对应的哈希值&＃xff0c;从而可以在O&＃xff08;n&＃43;m&＃xff09;时间内完成字符串匹配。在实现时&＃xff0c;可以用64位无符号整数计算哈希值&＃xff0c;并取h等于2^64&＃xff0c;通过自然溢出省去求模运算。

typedef unsigned long long ull;
const ull b&＃61;100000007;//哈希的基数&＃xff1b;
//a是否在b中出现
bool contain(string C,string S)
{int m&＃61;C.length(),n&＃61;S.length();if(m>n) return false;//计算b的m次方ull t&＃61;1;for(int i&＃61;0;ib;//计算C和S长度为m的前缀对应的哈希值ull Chash&＃61;0,Shash&＃61;0;for(int i&＃61;0;iC[i];for(int i&＃61;0;iS[i];//对S不断右移一位&＃xff0c;更新哈希值并判断for(int i&＃61;0;i&＃43;m<&＃61;n;i&＃43;&＃43;){if(Chash&＃61;&＃61;Shash) return true;//S从位置i开始长度为m的字符串子串等于C&＃xff1b;if(i&＃43;mm];}return false;
}

滚动哈希&＃xff08;Rabin-Karp算法&＃xff09;

 

---

 

hash( txt[s&＃43;1 .. s&＃43;m] ) &＃61; ( d ( hash( txt[s .. s&＃43;m-1]) – txt[s]*h ) &＃43; txt[s &＃43; m] ) mod q

hash( txt[s .. s&＃43;m-1] ) : Hash value at shift s.
hash( txt[s&＃43;1 .. s&＃43;m] ) : Hash value at next shift (or shift s&＃43;1)
d: Number of characters in the alphabet
q: A prime number
h: d^(m-1)

/* Following program is a C implementation of Rabin Karp
Algorithm given in the CLRS book */
#include
#include<string.h>// d is the number of characters in the input alphabet
#define d 256/* pat -> patterntxt -> textq -> A prime number
*/
void search(char pat[], char txt[], int q)
{int M &＃61; strlen(pat);int N &＃61; strlen(txt);int i, j;int p &＃61; 0; // hash value for patternint t &＃61; 0; // hash value for txtint h &＃61; 1;// The value of h would be "pow(d, M-1)%q"for (i &＃61; 0; i 1; i&＃43;&＃43;)h &＃61; (h*d)%q;// Calculate the hash value of pattern and first// window of textfor (i &＃61; 0; i ){p &＃61; (d*p &＃43; pat[i])%q;t &＃61; (d*t &＃43; txt[i])%q;}// Slide the pattern over text one by onefor (i &＃61; 0; i <&＃61; N - M; i&＃43;&＃43;){// Check the hash values of current window of text// and pattern. If the hash values match then only// check for characters on by oneif ( p &＃61;&＃61; t ){/* Check for characters one by one */for (j &＃61; 0; j ){if (txt[i&＃43;j] !&＃61; pat[j])break;}// if p &＃61;&＃61; t and pat[0...M-1] &＃61; txt[i, i&＃43;1, ...i&＃43;M-1]if (j &＃61;&＃61; M)printf("Pattern found at index %d \n", i);}// Calculate hash value for next window of text: Remove// leading digit, add trailing digitif ( i M ){t &＃61; (d*(t - txt[i]*h) &＃43; txt[i&＃43;M])%q;// We might get negative value of t, converting it// to positiveif (t <0)t &＃61; (t &＃43; q);}}
}/* Driver program to test above function */
int main()
{char txt[] &＃61; "GEEKS FOR GEEKS";char pat[] &＃61; "GEEK";int q &＃61; 101; // A prime number
search(pat, txt, q);return 0;
}

 

参考资料&＃xff1a;http://www.geeksforgeeks.org/archives/11937

参考资料&＃xff1a;http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap34.htm

http://www.cnblogs.com/feature/articles/1813967.html &＃xff08;翻译PKU