字符串匹配的 KMP算法

发布时间:2017-7-1 10:48:31编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"字符串匹配的 KMP算法 ",主要涉及到字符串匹配的 KMP算法 方面的内容,对于字符串匹配的 KMP算法 感兴趣的同学可以参考一下。

一般字符串匹配过程

KMP算法是字符串匹配算法的一种改进版,一般的字符串匹配算法是:从主串(目标字符串)模式串(待匹配字符串)的第一个字符开始比较,如果相等则继续匹配下一个字符, 如果不相等则从主串的下一个字符开始匹配,直到模式串被匹配完,则匹配成功,或主串被匹配完且模式串未匹配完,则匹配失败。匹配过程入下图:

这种实现方式是最简单的, 但也是低效的,因为第三次匹配结束后的第四次和第五次是没有必要的

分析

第三次匹配在j = 0(a)i = 2(a)处开始,在j = 4(c)i = 6(b)处失败,这意味着模式串和主串中:j = 0(a)i = 2(a)j = 1(b)i = 3(b)j = 2(c)i = 4(c)j = 3(a)i = 5(a)这四个字符相互匹配。

分析模式串的前3个字符:模式串的第一个字符j = 0是aj = 1(b)j = 2(c)这两个字符和j = 0(a)不同,因此以这两个字符开头的匹配必定失败,在第三次匹配中,主串中i = 3(b)i = 4(c)和模式串j = 1(b)j = 2(c)相互匹配,因此匹配失败后,可以直接跳过主串中i = 3(b)i = 4(c)这两个字符的匹配。

继续分析模式串的j = 3(a)j = 4(c)这两个字符,如果模式串匹配到j = 4(c)这个字符才失败的话,因为j = 4(c)的前一个字符j = 3(a)和第一个字符j = 0(a)是相同的,结合上一个分析得知:

1):下一次匹配中主串已经跳过了和j = 3(a)前两个相互匹配的字符i = 3(b)i = 4(c),将从i = 5(a)开始匹配。 
2):j = 3(a)i = 5(a)相互匹配。



上一篇:Keil MDK 5代码补全功能设置
下一篇:转: 将Eclipse代码导入到AndroidStudio的两种方式 ,测试了方法2,成功。

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款