朴素的字符串匹配算法为什么慢? 因为它太健忘了,前一次匹配的信息其实可以有部分可以应用到后一次匹配中的,而朴素的字符串匹配算法只是简单的把这个信息扔掉,从头再来,因此,浪费了时间。好好的利用这些信息,自然可以提高运行速度。
1.问题描述
给定目标字符串 T[0..n-1] (基于 0 的数组,数组长度为 n ),和模式串 P[0..m-1] ,问 P 可否匹配 T 中的任意子串,如果可以,返回匹配位置。
2.问题分析
直观分析
brute-force 的蛮力法,适用于较小规模的字符串匹配。
优化
主要介绍 3 种优化办法,分别具体为: Rabin-Karp 算法,有限自动机和 KMP 算法。将分为 3 篇博文分别讨论。
3.算法描述
Rabin-Karp 算法。
Rabin-Karp 算法(以下简称为 RK 算法),是基于这样的思路:即把串看作是字符集长度进制的数,由数的比较得出字符串的比较结果。例如,给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ,∑长度为 d=10 ,那么任何以∑为字符集的串都可看作 d (此处为 10 )进制的数。
记模式串 P[0..n-1] 对应的数值为 P , T[0..n-1] 所有长度为 m 的子串对应的数值为 ts ,设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。
那么, ts 即为 T[s..s+m] 对应的数值,这里 0<=s<=n-m-1 。
P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))
同样 t0 也可类似求得。
最重要的是如何从 ts 求出 ts+1 。
ts+1 =T[s+m]+d*(ts -dm-1 *T[s])
注:此处是该算法的关键,即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象,举个例子就比较明白了,设 x=12345 ,现在是已知长度为 3 的数值 234 ,现在要求 345 对应的数值,可以这样来得到: 345 = 5 + 10*(234-102 *2)
求出所有 m 长度子串所对应的数值,对数值进行比较,继而得出子串是否匹配。当模式串长度很大时,这时对应的数值会很大,比较起来比较麻烦,可使用对一个大奇数取模后进行比较。
4.具体实现
这里实现的只是m值较小时的情形,大整数需要特定的类的支持(如可自定义大整数类),选取10进制的数是为了方便起见,当然字母也是OK的。
#include <iostream>
using namespace std;
int getV(char p, const char* set)
{
for(int i=0; i<strlen(set); i++)
{
if (p==set[i])
return i;
}
return -1;
}
int RK(const char* T, const char* P,const char* set)
{
int base = strlen(set) ;
int n = strlen(T);
int m = strlen(P);
int h = 1;
for(int i=0;i<m-1;i++)
h*=base;
int p = 0;
int t = 0;
for(int i=0; i<m; i++)
{
p = base*p + getV(P[i],set);
t = base*t + getV(T[i],set);
}
for (int i=0; i<=n-m; i++)
{
cout<<"p,t is "<<p<<","<<t<<endl;
if (p==t) return i;
if (i<n-m)
t = getV(T[i+m],set)+base*( t - h*getV(T[i],set) );
}
return -1;
}
int main()
{
// set is the character set
const char* set= "0123456789";
const char* T = "258569236589780";
const char* P = "2365";
int i = RK(T, P, set);
cout<<"the postition is:"<<i<<endl;
return 0;
}
分享到:
相关推荐
该算法实现了数字字符的匹配,当数字字符相应的十进制数过大时,为了降低匹配的时间复杂度,使用数论中的模运算优化。
Rabin-Karp算法,是由M.O.Rabin和R.A.Karp设计实现的一种基于移动散列值的字符串匹配算法。 通常基于散列值的字符串匹配方法:(1)首先计算模式字符串的散列函数;(2)然后利用相同的散列函数计算文本中所有可能...
通过改进Karp-Rabin 算法,实现了多模式字符串匹配技术,实验表明多模式Karp-Rabin算法具有良好的性能。随后在多模式Karp-Rabin 算法的基础上进一步改进,使其在高并发情况下能够支持模式串动态增删功能。实验表明该...
运用Karp算法实现字符串匹配的c++程序
素字符串匹配算法(Naive String Matching) KMP 算法(Knuth-Morris-Pratt) Rabin-Karp 算法 Boyer-Moore 算法 A* 搜索算法 Dijkstra 算法 Bellman-Ford 算法 Floyd-Warshall 算法 Kruskal 算法 Prim 算法 Edmonds...
Rabin-Karp子串匹配实验室 匹配两个输入文件并输出具有几种规格化的文件; 使用Rabin Karp子字符串匹配和Bloom过滤器算法,哈希表实现。
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...
字符串搜索KMP、Boyer Moore、Rabin Karp等流行字符串匹配算法的java实现
字符串匹配 - Knuth–Morris–Pratt(KMP) 字符串匹配 - Rabin-Karp 优先队列 04_Advanced_Data_Structure 陷阱 段树 二叉索引树 特里 展开树 05_Classic_Algorithm_Series 01_LCA_and_RMQ 01 RMQ稀疏表 02 RMQ 段树 ...
扩展矩阵leetcode 算法 二分搜索(完成):, 快速排序(完成): 合并排序(完成): 后缀数组:, , , , Knuth-Morris-Pratt 算法 ...Rabin-Karp 算法: ...算法: ...算法: ...算法: ...字符串匹配算法: , , ,
快速关键字匹配- Rabin-Karp 算法被称为字符串搜索匹配的最新技术。 我已经实现了关键字匹配的 Rabin-Karp 想法。 用例是检查文档是否包含黑名单或白名单中的单词。 供您参考:1- 2-
:递归,快速排序 :lambda表达式,高阶函数,Matrix类,文件处理 :哈希函数,哈希表,查找重复的子字符串 :链表,迭代器,生成器 :用于字符串匹配的Rabin-Karp算法 :霍夫曼代码 :LZ压缩 :图像处理,去噪算法...
字符串匹配 幼稚的。 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包含用于里程...
Sharir,Kruskal,Prim,Dijkistra,Bellman-Ford,Ford-Fulkerson,LSD基数排序,MSD基数排序,3路基数快速排序,多路尝试,三元搜索尝试,Knuth-Morris-Pratt,Boyer-Moore,Rabin-Karp,正则表达式匹配,游程编码...
路基数快速排序、多路尝试、三元搜索尝试、Knuth-Morris-Pratt、Boyer-Moore、Rabin-Karp、正则表达式匹配、游程编码、霍夫曼编码、LZW 压缩和 Burrows-Wheeler 变换。 第二部分还介绍了归约和难处理,包括 P = NP ...