文档章节

String indexOf 之BF、KMP算法

陶邦仁
 陶邦仁
发布于 2012/11/26 23:34
字数 664
阅读 1043
收藏 10
点赞 1
评论 0

一. 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

© 著作权归作者所有

共有 人打赏支持
陶邦仁
粉丝 1556
博文 388
码字总数 1483822
作品 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 ⋅ 0

算法分析_Index

常用算法 String indexOf 之BF、KMP算法 非递归方法实现对TB级文件目录的全遍历 一道新浪面试算法题,两行代码搞定,有兴趣的看看 斐波那契数列:一道100年后羊圈羊的数量算法题 白话算法 白...

陶邦仁 ⋅ 2014/03/24 ⋅ 0

数据结构与算法JavaScript (四) 串(BF)

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

文艺小青年 ⋅ 2017/06/29 ⋅ 0

数据结构与算法JavaScript (五) 串(经典KMP算法)

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

文艺小青年 ⋅ 2017/06/01 ⋅ 0

KMP (KMP+拓展KMP)算法总结

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

my_sunshine26 ⋅ 2017/05/28 ⋅ 0

java面试冷知识 string的indexof

java中String的玩法还真多,本文介绍的的是indexof这个查找字串的实现。 说到查找子串,最原始的算法就是先找到第一个字符是匹配的,然后从这个字符串开始往后比对,直到和子串完全匹配。很多...

xpbob ⋅ 2016/04/16 ⋅ 0

模式匹配算法

《数据结构(C语言版)》上给出了两种模式匹配算法,BF算法和KMP算法。 存在一个主串S和一个模式T,要在主串S中查找与模式T相匹配的子串。 BF算法 操作步骤: 分别利用计数指针和 指示主串和...

流氓兔来啦 ⋅ 2016/11/06 ⋅ 0

模式匹配- KMP算法

■Knuth-Morris-Pratt(KMP)算法-听我的,别总重来。 发表于1977年的KMP算法是一种高效的匹配算法,消除了BF算法中回溯问题,即每次移动的距离可以不是1而是更大的数,也不需要回溯,BF算法...

壶漏子 ⋅ 2015/05/27 ⋅ 0

MatcherDroid-类正则表达式匹配自动机,更高效率,更好中文支持

What’s MatcherDroid 因为不爽正则表达式复杂的语法,较低的中文支持度,不是很好的效率,所以自己写了一个类正则表达式的自动匹配/提取机。目前测试来看,MatcherDroid相较于正则表达式,有...

wxyyxc1992 ⋅ 2013/11/30 ⋅ 1

模式匹配——从BF算法到KMP算法

模式匹配 子串的定位操作通常称为串的模式匹配。模式匹配的应用很常见,比如在文字处理软件中经常用到的查找功能。我们用如下函数来表示对字串位置的定位: int index(const string &Tag,co...

huang19015 ⋅ 2014/06/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

那些证书相关的玩意儿(SSL,X.509,PEM,DER,CRT,CER,KEY,CSR,P12等)

之前没接触过证书加密的话,对证书相关的这些概念真是感觉挺棘手的,因为一下子来了一大堆新名词,看起来像是另一个领域的东西,而不是我们所熟悉的编程领域的那些东西,起码我个人感觉如此,且很长...

颖辉小居 ⋅ 18分钟前 ⋅ 0

利用有限制通配符提升API灵活性(28)

1、参数化类型是不可变的 List<String> 不是List<Object>的子类,但是二者是有联系的 利用有限制的通配符类型处理类似情况 List<? extends Object>(生产者) Collection<? super E>(消费者......

职业搬砖20年 ⋅ 24分钟前 ⋅ 0

ssm框架 +bootstrap分页

这里有两种方式 方式一:自己写分页 方式二:使用插件PageHelper 1.自己写分页 1.1 效果 1.2 实现过程 1.2.1 创建分页公共类 //---------------------------1.属性-------------------------...

Lucky_Me ⋅ 31分钟前 ⋅ 0

Istio

helm template install/kubernetes/helm/istio --name istio --namespace istio-system > $HOME/istio.yaml after $ kubectl create namespace istio-system$ kubectl create -f $HOME/ist......

openthings ⋅ 31分钟前 ⋅ 0

内核线程、轻量级进程、用户线程

线程与进程概念 在现代操作系统中,进程支持多线程。 进程是资源管理的最小单元; 线程是程序执行的最小单元。 即线程作为调度和分配的基本单位,进程作为资源分配的基本单位 一个进程的组成...

117 ⋅ 36分钟前 ⋅ 0

elasticsearch2.4.6升级为elasticsearch-5.5.0的经历

将elasticsearch-5.5.0 中的配置 path.data 指向原来的数据路径 即 path.data: /usr/local/src/elasticsearch-2.4.6/data 注意: elasticsearch-5.5.0 需要将jdk版本升级到1.8...

晨猫 ⋅ 37分钟前 ⋅ 1

lvm讲解 磁盘故障小案例

1

oschina130111 ⋅ 41分钟前 ⋅ 0

那些提升开发人员工作效率的在线工具

本文转载自公众号 Hollis 作为一个Java开发人员,经常要和各种各样的工具打交道,除了我们常用的IDE工具以外,其实还有很多工具是我们在日常开发及学习过程中要经常使用到的。 Hollis偏爱使用...

时刻在奔跑 ⋅ 53分钟前 ⋅ 0

restful风格 实现DELETE PUT请求 的web.xml的配置

import org.springframework.beans.factory.annotation.Autowired; import org.springframework.http.HttpStatus; import org.springframework.http.ResponseEntity; import org.springframe......

泉天下 ⋅ 58分钟前 ⋅ 0

Shell数组

Shell数组 Shell在编程方面比Windows批处理强大很多,无论是在循环、运算。 bash支持一维数组(不支持多维数组),并且没有限定数组的大小。类似与C语言,数组元素的下标由0开始编号。获取数...

蜗牛奔跑 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部