文档章节

KMP算法心得

WhiteFish
 WhiteFish
发布于 2015/08/25 00:07
字数 575
阅读 137
收藏 19

KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题。算法名称来源于发明者Knuth,Morris,Pratt。

假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm)。

朴素的字符串查找方法

      从字符串S的第一个字符开始与M进行比较,如果匹配失败。从下一字符开始,重新比较。指导第 (ls - lm) 个字符。

这种方法容易想到并且容易理解,效率不高。

     问题在于每次匹配失败后,移动的步伐固定为 1其实步子可以迈得再大一些。


KMP的字符串查找方法

     假定在模式串的连续字串M[0, i] 且 i < lm,已经成功匹配字符串S。但是不巧第 i+1 个字符失败了,怎么办?移动一个字符,重头再来?当然不好,那就是朴素路线了。我们能否从跌倒的地方继续走呢?

     既然字串M[0 - i]已经匹配成功,那就从这个子串上做文章。举个栗子     

S序号
j
j + 1
 j + 2
j + 3
j + 4
j + 5
 j+6
j + 7
。。。
S串
a
b
c
a
b
c
d
e
。。。
M串
a
b
c
a
b
d



M序号

0
1
2
3
4
5



此时匹配失败在M串的第5个字符,前4个字符已经匹配成功。

如果从跌倒的地方出发,则需要存在M[0, 4]的子串M[0, k] == S[j+4-k , j+4]。

由于M[0, 4] == S[j ,  j+4] 则有 字串S[j+4-k, j+4] == M[4-k, 4]。综上有M[0, k] == M[4-k, 4]

如果这样的k不存在,那就老老实实的朴素了


从上面的表格可以直观的看出,下一次匹配只要把M串移动到 j + 3 位置,从 j+5 开始匹配就可以。很容易看出来 在已经匹配成功的字串M[0 , 4]中有最长的子串 (M[0 , 1] == M[3 , 4]),这个就是问题的关键。

因此KMP的核心部分就是计算模式串的各个串的 k


© 著作权归作者所有

共有 人打赏支持
下一篇: Redis事件驱动
WhiteFish
粉丝 2
博文 3
码字总数 1035
作品 0
西城
技术主管
私信 提问
KMP算法详解, 关于NEXT数组及其改进

关于KMP的总结 1.nextval数组 具体含义: abcdefabc 在第二个c处匹配失败 则应将j匹配到c上 即为j = 2 = 最大部分匹配长度; 这里给出代码 void get_nextval(){nextval[0] == -1; //初变量不...

QwQSQFY
2017/07/29
0
0
数据结构与算法JavaScript (五) 串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右...

文艺小青年
2017/06/01
0
0
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.4K
0
KMP (KMP+拓展KMP)算法总结

KMP及拓展KMP算法 KMP算法是一种线性时间复杂度的字符串匹配算法,它是对BF(Brute-Force,最基本的字符串匹配算法)的改进。对于给定的原始串S和模式串T,需要从字符串S中找到字符串T出现的位...

my_sunshine26
2017/05/28
0
0
String indexOf 之BF、KMP算法

一. BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二...

陶邦仁
2012/11/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day11

architect刘源源
今天
6
0
论学好Linux系统的超级重要性

不知道各位在日常的工作生活中有没有接触过“rm -rf /*”这个命令,因为这个命令搞出来的事情可还不少呢!前段时间就在一个群里看到了有个小伙子,老板让他去维护一下服务器,这小伙也不太懂...

Linux就该这么学
昨天
6
0
git 使用

1,首先在github配置好信息和仓库,然后在本地进行操作 git init git config user.name 'zhangwuer' git config user.email '56789053@qq.com' 2,与远程分支建立连接 git checkout -b test......

天王盖地虎626
昨天
3
0
git checkout 命令详解

在日常的git操作中,git checkout——检出,是我们的常用命令。最为常用的两种情形是创建分支和切换分支。 在下面的命令中,使用了一些简写,在这里说明一下: git st # git statusgit ci ...

shzwork
昨天
10
0
【Nginx】Nginx多级代理,获取客户端真实请求IP以及每级代理IP

Nginx多级代理,获取客户端真实请求IP以及每级代理IP 如图所示,每一级nginx里的location配置里需要加上对应的配置,最后一级nginx是直接到应用,测试时为了方便,直接用echo模块去测试,打印...

薛定谔的旺
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部