Python实现KPM算法详解
知识点说明:
先说前缀,和后缀吧
比如有一个串:abab
则在下标为3处的(前缀和后缀都要比下标出的长度小1,此处下标为3出的长度是4)
前缀为:a,ab,aba
后缀为:b,ba,bab
一、要获取KPM算法的next[]数组
简单说一下原理吧,首先k,用来存放前缀的下标,首先初始化j=0(j用来表示模式串的下标,一直去模式串的每一位与前面的进行比较,如果相等,则记录下当前位置与前面的哪个位置相同,我们这里主要是要记录相同位置的下一个位置,就是不相同的位置,从不相同的位置开始比较,就是回溯到不相同位置,所以这里在t[j]==t[k]成立的时候要j+1,为了比较下一个位置是否相同,k也要+1),模式串从0开始,k=-1,next[0]=-1第一个位置赋默认值-1;
此处串采用=“abab”
第一次循环:
判断k是否等于-1,如果等于则,j和k都+1,
此时j=1,k=0,next[1]=0,也就是第2个位置(下标1)的回溯位置还是0,因为前缀的最大长度必须小于当前位置的长度;
第二次循环:
j=1,k=0,next[1]=0;k已经不等于-1了,判断t[j]==t[k],t[1]==t[0],t[1]="b",t[0]="a",不相等
执行else:
k=next[0]=-1
第三次循环:
k==-1
j和k都+1,j=2,k=0,next[2]=0
第四次循环:
k不等于-1,判断t[2]==t[0],t[2]=“a”=t[0]=“a”,成立
j和k都+1,j=3,k=1,next[3]=1
此时next=[-1,0,0,1],next[3]=1表示在next[3]处发生不匹配时,也就是模式串下标为3时为“b”,说明前面aba都是和目标串都匹配,所以模式串不匹配位置前面的串aba一定与目标串不匹配位置前面的前3个值相等,也就是aba,所以此刻,只需要回溯到模式串的1位置,也就是模式串的b,模式串b前面是a,满足目标串的前一个a。
第五次循环:
k依旧是不等于-1,就是比较上一个位置后面的两个数再进行比较,简单的说,以此取出每一项与第一项比较,如果存在相等的就再比较下一个与第二项是否相等。
代码如下:
def GetNext(t, next): j, k = 0, -1 next[0] = -1 while j < len(t) - 1: if k == -1 or t[j] == t[k]: # 如果k==-1 或者 开始位置和结尾位置有相同的元素 j, k = j + 1, k + 1 # j和k都加1,当前位匹配,则从下一个位置开始匹配,所以k+1;j再进行取下一位判断是否也是匹配,所以也要+1 next[j] = k # 当前位置要取k项 else:#如果不相等,再把k置-1,下一次循环再进行+1操作,j这个位置再存入0,表示无匹配项 k = next[k] return next
二、KMP函数
原理和BF算法是一样的,唯独不同的是,当模式串与目标串不匹配的时候,不直接回溯模式串,而是根据模式串的next[]表,查询要回溯到的位置,直接回溯到模式串的指定位置,KMP算法的核心也就在这里,但是这种方法一般只对前缀和后缀存在相同元素时,有效果,也就是说相同部分是一样的就不再进行比较了,从相同元素的下一个位置开始比较,所以KMP算法最复杂的部分其实就是找next[]表,要找出模式串的每一个位置,是否有相同前缀,如果有则标注该相同位置,下次回溯就不用回溯到0这个位置,可以从不相同位置开始。
def KMP(s, t): next = [0] * len(t) next = GetNext(t, next) print(next) i, j = 0, 0 while i < len(s) and j < len(t): if j == -1 or s[i] == t[j]: i, j = i + 1, j + 1 else: j = next[j] if j >= len(t): return i - len(t) else: return -1
完整代码:
def GetNext(t, next): j, k = 0, -1 next[0] = -1 while j < len(t) - 1: if k == -1 or t[j] == t[k]: # 如果k==-1 或者 开始位置和结尾位置有相同的元素 j, k = j + 1, k + 1 # j和k都加1,当前位匹配,则从下一个位置开始匹配,所以k+1;j再进行取下一位判断是否也是匹配,所以也要+1 next[j] = k # 当前位置要取k项 else:#如果不相等,再把k置-1,下一次循环再进行+1操作,j这个位置再存入0,表示无匹配项 k = next[k] return next def KMP(s, t): next = [0] * len(t) next = GetNext(t, next) print(next) i, j = 0, 0 while i < len(s) and j < len(t): if j == -1 or s[i] == t[j]: i, j = i + 1, j + 1 else: j = next[j] if j >= len(t): return i - len(t) else: return -1 if __name__ == '__main__': re = KMP('asdfghjsssaaasdfaaaabababcdabd', "ababaaaababaa") print(re)
结果:
到此这篇关于Python实现KPM算法详解的文章就介绍到这了,更多相关Python KPM算法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/baidu_39105563/article/details/1217541
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了Python绘制的爱心树与表白代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-06