问题描述:
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
分享到:
相关推荐
该算法实现了数字字符的匹配,当数字字符相应的十进制数过大时,为了降低匹配的时间复杂度,使用数论中的模运算优化。
Rabin-Karp算法,是由M.O.Rabin和R.A.Karp设计实现的一种基于移动散列值的字符串匹配算法。 通常基于散列值的字符串匹配方法:(1)首先计算模式字符串的散列函数;(2)然后利用相同的散列函数计算文本中所有可能...
通过改进Karp-Rabin 算法,实现了多模式字符串匹配技术,实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进,使其在高并发情况下能够支持模式串动态增删功能。实验表明该...
运用Karp算法实现字符串匹配的c++程序
Rabin-Karp子串匹配实验室 匹配两个输入文件并输出具有几种规格化的文件; 使用Rabin Karp子字符串匹配和Bloom过滤器算法,哈希表实现。
素字符串匹配算法(Naive String Matching) KMP 算法(Knuth-Morris-Pratt) Rabin-Karp 算法 Boyer-Moore 算法 A* 搜索算法 Dijkstra 算法 Bellman-Ford 算法 Floyd-Warshall 算法 Kruskal 算法 Prim 算法 Edmonds...
Google传教士Checkmaster 1>在JAVA中使用基于JSoup的Web爬网。 2>实现了Rabin-Karp字符串匹配算法。
本资源为BT文件,下载速度快,如果P2P工具... 多路尝试法, 三元查找尝试法, Knuth-Morris-Pratt算法, Boyer-Moore算法, Rabin-Karp算法, 正则匹配, run-length编码, Huffman编码, LZW压缩, 还有Burrows-Wheeler变换。
##字符串匹配算法 朴素算法 Rabin-Karp算法 KMP算法 #数据结构 ##树 二叉树 使用左孩子右兄弟实现的多叉树 二叉搜索树 红黑树 动态顺序统计树 区间树 AVL树(未实现,类似于红黑树) Tries(用于处理字符串) B树(B...
字符串匹配 - Knuth–Morris–Pratt(KMP) 字符串匹配 - Rabin-Karp 优先队列 04_Advanced_Data_Structure 陷阱 段树 二叉索引树 特里 展开树 05_Classic_Algorithm_Series 01_LCA_and_RMQ 01 RMQ稀疏表 02 RMQ 段树 ...
:递归,快速排序 :lambda表达式,高阶函数,Matrix类,文件处理 :哈希函数,哈希表,查找重复的子字符串 :链表,迭代器,生成器 :用于字符串匹配的Rabin-Karp算法 :霍夫曼代码 :LZ压缩 :图像处理,去噪算法...
字符串搜索KMP、Boyer Moore、Rabin Karp等流行字符串匹配算法的java实现
快速关键字匹配- Rabin-Karp 算法被称为字符串搜索匹配的最新技术。 我已经实现了关键字匹配的 Rabin-Karp 想法。 用例是检查文档是否包含黑名单或白名单中的单词。 供您参考:1- 2-
扩展矩阵leetcode 算法 二分搜索(完成):, 快速排序(完成): 合并排序(完成): 后缀数组:, , , , Knuth-Morris-Pratt 算法 ...Rabin-Karp 算法: ...算法: ...算法: ...算法: ...字符串匹配算法: , , ,
字符串匹配 幼稚的。 Rabin-Karp。 克努斯·莫里斯·普拉特(Knuth-Morris-Pratt)。 博耶·摩尔·霍尔普尔(Boyer-Moore-Horspool)。 细绳 将字符串转换为整数,而不在完整字符串上使用int。 包含单词的反向...
二叉搜索树,红黑树,平衡树)红黑树,开头树堆,图基本算法排序算法(堆排序,快排,归并,冒泡)朴素匹配,Rabin-Karp算法(节省m的计算时间),kmp字符串匹配算法图算法(最小生成树,最短路径,深度搜索(完成一...
2 7 模式匹配算法:Rabin–Karp 算法 38 2 8 字符串的最长回文子串:Manacher 算法 42 第 3 章 序列 44 3 1 网格中的最短路径 44 3 2 编辑距离(列文斯登距离45 3 3 最长公共子序列 47 3 4 升序最长子序列 49 3 5 两...
使用KMP,LCSS和Rabin-Karp字符串匹配算法为COSC320制作的抄袭检测器。 档案资讯 g17_corpusfinal/包含我们用于该项目的数据集中的所有文件。 所有文件均为.txt文件格式。 COSC320ThirdMilestone.ipynb包含用于里程...
| KARP-RABIN 字符串匹配 32 | 基于 KARP-RABIN 的字符块匹配 32 | 函数名: STRSTR 32 | BM 算法的改进的算法 SUNDAY ALGORITHM 32 | 最短公共祖先(两个长字符串) 33 | 最短公共祖先(多个短字符串) 33 ...
32.2 Rabin\Karp算法 32.3 利用有限自动机进行字符串匹配 32.4 Knuth?Morris?Pratt算法 思考题 本章注记 第33章 计算几何学 33.1 线段的性质 33.2 确定任意一对线段是否相交 33.3 寻找凸包 ...