`
dogasshole
  • 浏览: 836333 次
文章分类
社区版块
存档分类
最新评论

字符串匹配之Rabin-Karp算法

 
阅读更多

问题描述:

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

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


代码示例:

参考资料:http://www.iteye.com/topic/287105


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


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

递推式是如下这个式子:

ts+1=(d(ts-T[s+1]h)+T[s+m+1])modq

例如,如果d=10(十进制)m=5,ts=31415,我们希望去掉最高位数字T[s+1]=3,再加入一个低位数字(假定T[s+5+1]=2)就得到:

ts+1=10(31415-1000*3)+2=14152


代码示例:




参考资料:http://www.geeksforgeeks.org/archives/11937


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

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics