博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
KMP算法详解
阅读量:5914 次
发布时间:2019-06-19

本文共 1893 字,大约阅读时间需要 6 分钟。

一直以来对KMP算法理解的不是很透彻。看了左神的程序员代码面试指南后感觉基本明白了。

我们都知道KMP算法最重要的是next数组,next[i]的含义是在match[i]之前的字符串match[0..i-1]中,必须以match[i-1]结尾的后缀子串(不能包含match[0])与必须以match[0]开头的前缀子串(不能包含match[i-1])最大匹配长度是多少。比如match="aaaab",我们来求一下next[4],match[4]=='b',它之前的字符串为"aaaa",根据定义它的后缀子串和前缀子串的最大匹配为"aaa",所以next[4]=3.

假设从str[i]出发,匹配到j位置时发现与match中的字符不一致,此时,我们利用next数组,next[j-i]表示match[0..j-i-1]这一段字符串前缀与后缀的最长匹配。假设前缀是a区域这一段,后缀是b区域这一段,再假设a区域的下一个字符是match[k],如图所示。

那么下次匹配时直接让str[j]与match[k]进行匹配。相当于match向右滑动。如果match滑到最后也没匹配出来,就说明str中没有match,为什么这样做是正确的呢?

如图,匹配到A字符和B字符才发生的不匹配,所以c区域等于b区域,有next数组可知b区域与a区域相等,所以直接把字符C滑到A的位置开始匹配即可,那么为什么中间这一段是不用检查的呢?

假设d区域开始的字符是不用检查区域的一个位置,如果从这个位置开始能够匹配出match,那么显然d区域和e区域相等,假设d区域对应到match中是d'区域,也就是字符B之前字符串的后缀,而e是match的前缀,随意对match来说,相当于找到了B字符之前字符串的一个比a,b区域更的大前缀与后缀匹配长度,这与next数组的值是自相矛盾的,因为next数组保存的就是最大前缀与后缀匹配长度,所以如果next数组的值计算正确,这种情况绝对不会发生。

匹配过程代码

int getIndexOf(string& s,string& m){    if(s.length()
next=getNext(m); while(si
next数组的求解

对match[0]来说,在它之前没有字符,说以next[0]规定为-1。对match[1]来说,它只用长度为0的前后缀,所以next[1]为0。之后对于match[i](i>1)来说:

1.因为是从左到右求解next数组,所以在求next[i]的值时,前面的next值均已知。假设match[i]字符为A,match[i-1]为B,通过next[i-1]可以知道B字符前的最大前缀后缀匹配长度,分别为/和k区域。然后看字符C与B是否相等。

2.如果C与B相等,那么next[i]=next[i-1]+1

3.如果C与B不相等,就看字符C之前的前缀后缀匹配情况,假设C是第cn个字符,那么next[cn]就是其最长前缀后缀匹配长度。

如图,m和n区域为字符C之前字符串的最长匹配的前缀后缀区域,m'区域为k区域最右且长度与m区域相同,因为k区域和/区域是相等的,所以m和m'区域也相等,字符D为n区域后的一个字符,接下来比较字符D与B是否相等。

1)如果相等,那么next[i]=next[cn]+1。

2)如果不等,继续往前跳到字符D,之后的过程与跳到字符C类似,一直进行这样跳的过程,只要有相等的情况,next[i]的值就能确定。

4.如果跳到match[0]的位置,说明字符A之前的字符串不存在前缀后缀匹配的情况,则令next[i]=0。

求解next数组代码

vector
getNext(string& ms){ vector
next(ms.length()); if(ms.length()==1){ next[0]=-1; return next; } next[0]=-1; next[1]=0; int pos=2; int cn=0; while(pos
0) cn=next[cn]; else next[pos++]=0; } for(int i=0;i

转载于:https://www.cnblogs.com/nickqiao/p/7583337.html

你可能感兴趣的文章
JDBCRealm Http Digest
查看>>
CentOS 7 网络配置
查看>>
matplotlib 交互式导航
查看>>
eclipse的插件未安装成功
查看>>
由装箱引发的——Integer比较的来龙去脉
查看>>
java 深拷贝
查看>>
UnicodeEncodeError: 'ascii' codec can't encode
查看>>
jvm在什么时候进行进行垃圾回收,在什么时候进行扩大内存
查看>>
【转载】强大的命令行工具wmic
查看>>
JavaScript里的数组转化新方法Array.From
查看>>
修改eclipse下maven项目的java文件编译目录路径
查看>>
ubuntu 安装 chef安装
查看>>
《JAVA面向对象的特征 》
查看>>
mongodb基础(1)
查看>>
php 笔试题汇总
查看>>
easyui-tree 修改图标
查看>>
一文带你快速了解,python是如何解析XML文件
查看>>
如何用30分钟快速优化家中Wi-Fi?阿里工程师有绝招
查看>>
云越发展,锁定问题就会越严重?
查看>>
什么样人适合学平面设计?零门槛入门工具收藏
查看>>