文档章节

String indexOf 之BF、KMP算法

陶邦仁
 陶邦仁
发布于 2012/11/26 23:34
字数 664
阅读 1.5K
收藏 10

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

一. BF算法

BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果

举例说明: S:  ababcababa  P:  ababa

BF算法匹配的步骤如下:

image

代码实现:

image

其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

二. KMP算法

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

对于next[]数组的定义如下:

1)next[j]=-1  j=0

2)next[j]=max k:0<k<j P[0...k-1]=P[j-k,j-1]

3)next[j]=0  其他

如:

P      a    b   a    b   a

j       0   1    2   3   4

next -1  0    0   1   2

即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]

因此KMP算法的思想就是:在匹配过程中,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。

代码实现如下:

image

因此KMP算法的关键在于求算next[]数组的值,即求算模式串每个位置处的最长后缀与前缀相同的长度, 而求算next[]数组的一种思路是用递推的思想去求算:

image

© 著作权归作者所有

陶邦仁
粉丝 1715
博文 420
码字总数 1483963
作品 0
海淀
技术主管
私信 提问
加载中

评论(0)

模式匹配-BF、KMP、JavaString.indexOf、BM大比拼

闲来无事,比比看。 / 模式匹配-BF、KMP、JavaString.indexOf、BM大比拼 / package javay.test; import javay.util.PMBF; import javay.util.PMBM; import javay.util.PMKMP; / 模式匹配-BF......

放个屁
2015/05/27
130
0
数据结构与算法JavaScript (四) 串(BF)

串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作CUR...

文艺小青年
2017/06/29
0
0
JavaScript 字符串匹配算法

原文链接 前言 字符串匹配算法,在日常开发中也常被频繁用到。当然,我们可以用正则匹配来完成字符串匹配,但是,学习和理解相关的字符串匹配算法,对于我们技术成长还是有很多好处的。 定义...

Checkson
2019/07/25
0
0
数据结构与算法JavaScript (五) 串(经典KMP算法)

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

文艺小青年
2017/06/01
0
0
字符串模式匹配算法--BF和KMP详解

1,问题描述 字符串模式匹配:串的模式匹配 ,是求第一个字符串(模式串:str2)在第二个字符串(主串:str1)中的起始位置。 注意区分: 子串:要求连续 (如:abc 是abcdef的子串) 子序列:可...

osc_xzljtcxj
2018/11/16
4
0

没有更多内容

加载失败,请刷新页面

加载更多

webpack.02-如何打包

在空文件夹初始化:CMD npm init -y -y意思是全部yes cnpm install -D webpack webpack-cli 文件结构 src(文件夹)--->index.js console.log('hello webpack') test(文件夹)--->main.js......

_qq507570355
17分钟前
22
0
希望多年运维的大佬能回答一下小弟心中的疑惑

小弟之前公司项目有搭建过一个数据中心,底层虚拟化系统,建设好之后配合开发人员完成好了各种项目环境的搭建。前期比较累一点,也负责各种日志备份,监控系统之类的搭建。当系统趋于稳定之后...

夜雨声声到天明
19分钟前
18
0
OSChina 周三乱弹 —— 只泡面不泡妞

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @Cobbage :分享许巍的单曲《我的爱 (慕思《觉/醒》视频主题曲)》: 《我的爱 (慕思《觉/醒》视频主题曲)》- 许巍 手机党少年们想听歌,请使劲...

小小编辑
41分钟前
24
0
【整体管理】开发人员KPI量化

1.代码规范。 衡量标准:各类的开发规范。 2.任务进度控制能力。 衡量标准:根据任务完成状况来测量。 3.完成质量。 衡量标准:是否发生重大的bug,bug的数量,及修复bug的响应能力。 4.沟通...

郭恩洲_OSC博客
今天
30
0
使用git clone命令克隆文件出现error: RPC failed相关错误

使用git clone命令克隆文件出现error: RPC failed; curl 18 transfer closed with outstanding read data remain问题 笔者最近在使用git clone命令从github克隆源码到电脑时出现了以下问题 ...

独钓渔
今天
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部