没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
首先对三种基本字符串匹配算法进行了详细分析和说明,再编程实现。创新拓展研究了Boyer-Moore算法,进行了分析和编程实现。让四种算法对数据量极大的文本,进行子串的查询处理,并分析算法运行时间效率,并对所有输出的匹配位置结果进行相互对比验证,以证明算法设计和实现的正确性。为了分析不同数据规模对不同算法的影响程度,通过改变文本的数据量大小,用相同的子串进行模式查找,通过对运行时间的比较以获得数据规模对算法的影响,并利用MATLAB绘制效率图进一步直观分析。
资源推荐
资源详情
资源评论










实现并对比三种基本的字符串匹配算法
--John Jiang
目录
问题描述............................................................ 2
需求分析............................................................ 2
假设和简化...................................................... 2
功能和运用...................................................... 3
算法和数据结构设计.................................................. 3
朴素匹配算法.................................................... 4
Rabin-Karp 算法................................................. 6
KMP 算法 ....................................................... 10
创新拓展研究................................................... 15
Boyer-Moore 算法........................................... 15
程序测试........................................................... 21
附录--完整源代码................................................... 26

问题描述
文本是一个长度为 n 的数组
1..Tn
,模式是一个长度为
mn
的数组
1..Pm
,T
和 P 中 的 元 素 都 属 于 有 限 的 字 母 表 Σ 表 ,如果
0 s n m −
,并且
1.. 1..T s s m P m+ + =
,即对 1≤j≤m,有 T[s+j] = P[j],则称模式 P 完成了
和 T 的匹配,且 P 在 T 中出现的位移为 s 并称 s 是一个有效位移。
比如上图中,目标是找出在文本 T = abcabaabcabac 中模式 P = abaa 的所有
出现有效位移。从图中易知该模式 P 在此文本 T 中仅出现一次,即在位移 s = 3
处,则位移 s = 3 是一个有效位移。
需求分析
假设和简化
用
*
表示包含所有有限长度的字符串的集合,该字符串是由字母表
中
的字符组成。长度为零的空字符串用
表示,也属于
*
。一个字符串
x
的长度
用
x
来表示。两个字符串
x
和
y
的连结用
xy
表示,长度为
xy+
,由
x
的字符
后接
y
的字符构成。如果对于某个字符串
y
*
有
x wy=
,则称字符串
w
是字
符串
x
的前缀,记作
wx
。如果
wx
,则
wx
。类似地,如果对于某个字符
串
y
有
x yw=
,则称字符串
w
是字符串
x
的后缀,记作
wx
。和前缀类似,如
果
wx
,则
wx
。例如,
ab abcca
和
cca abcca
。空字符串
同时是任何
一个字符串的前缀和后缀。对于任意字符串
x
和
y
以及任意字符
a
,当且仅当
xa ya
时,我们有
xy
。
为了使符号简结,模式
1..Pm
的由 k 个字符组成的前缀
1..kP
记作
k
P
。因

此,
0
P=
,
m
P =P=P 1..m
。与此类似,文本 T 中由 k 个字符组成的前缀记为
k
T
。
采用这种记号,我们能够把字符串匹配问题表述为:找到所有偏移
( )
0s s n m −
,
使得
sm
PT
+
。
功能和运用
在编辑文本程序过程中,经常需要在文本中找到某个模式的所有出现的位置。
典型的情况就是,一段正在被编辑的文本构成一个文件,而所要搜索的模式是用
户正在输入的特定的关键字,有效的解决这个问题的算法就是字符串匹配算法,
该算法能够极大提高编辑文本程序时的响应效率。
在其他很多应用中,字符串匹配算法用于在 DNA 序列中搜索特定的序列。在
网络搜索引擎中也需要用这种方法来找到所需要查询的网页地址。
算法和数据结构设计
通过查阅资料整理可得,解决字符串匹配的算法包括:朴素匹配算法(Naive
Algorithm)、 Rabin-Karp 算法、有限自动机算法(Finite Automation)、Knuth-
Morris-Pratt 算法(KMP Algorithm)、 Boyer-Moore 算法、Simon 算法、Colussi
算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法
和 Sunday 算法等。
基于本人的研究和理解,首先对其中三种基本的字符串匹配算法:朴素匹配
算法(Naive Algorithm)、 Rabin-Karp 算法、Knuth-Morris-Pratt 算法进行分
析实现,再合理进行创新拓展实现 Boyer-Moore 算法。

朴素匹配算法
算法设计与分析说明
朴素匹配算法又称为暴力匹配算法(Brute Force Algorithm), 是最原始也
最容易想到的算法,通过一个循环将模式 P 和文本 T 进行字符逐一的匹配,可以
形象的看成是用一个包含模式 P 的模板沿文本滑动,找到所有在范围 n-m+1 中
存在满足条件
1.. 1..P m T s s m= + +
的有效位移 s。当某一个字符不相匹配时,
将偏移量 s 加一,从头开始进行匹配。
算法设计思想实例说明
为形象具体的表达算法设计思想,通过如下的实例进行说明:
图 1
在图 1 中,对于模式 P = aab 和文本 T = acaabc,将模式 P 沿着 T 从左
到右滑动,逐个比较字符是否相等以判断模式 P 在文本 T 中是否存在,若存在
则返回偏移量 s 的值。
算法伪代码设计
根据如上的算法设计与分析以及实例说明,可以设计如下的伪代码,T 表示文本,
P 表示模式,第 1-2 行首先求出文本及模式的长度,第 3-5 行通过一个循环,s
从
0..nm−
逐 一 进 行 取 值 , 表 示 偏 移 量 , 如 果 在 某 一 个 偏 移 值 下 满 足
1.. 1..P m T s s m= + +
,则表示匹配成功,并将偏移量 s 输出。
NAIVE-STRING-MATCHER(T, P)
1 n←length[T]
2 m←length[P]
3 for s←0 to n-m
4 do if P[1..m]=T[s+1..s+m]
5 then print "模式匹配的偏移值 s=" s
算法程序设计(C++)
void naive_matcher(string t,string p) //模式 p 和文本 t 字符串
{
int n=t.length();

int m=p.length();//分别求出模式和文本的字符串长度
for(int s=0;s<=n-m;s++)//s 偏移量的循环
{
for(int i=0;i<m;i++) //模式串和文本进行字符的匹配
{
if(p[i]==t[s+i]&&i==m-1) printf("%d\n",s);
//当字符全部匹配,即达到了模式串的长度
else if(p[i]!= t[s+i]) break;
//只要有一个字符不相等,就停止内循环,改变外循环的偏移量 s
}`
}
return;//若不存在则返回-1
}
算法时间复杂度分析
通过分析易知,朴素匹配算法没有对模式 P 进行预处理,所以预处理的时
间为 0。通过外层的循环进行 n-m+1 次的偏移量 s 取值,对于每一个 s 取值,最
坏要进行 m 次 的 字 符 相 等 判 定 , 从 而 匹 配 的 时 间 在 最 坏 情 况 下 为
( )
( )
1n m m
−+
,并且当
2
n
m
=
,则为
( )
2
n
。
剩余33页未读,继续阅读
资源评论


JuyongJiang
- 粉丝: 283
- 资源: 5
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助


安全验证
文档复制为VIP权益,开通VIP直接复制
