本文实例讲述了Python实现字符串的KMP算法。分享给大家供大家参考，具体如下：
KMP算法Python实现
今天研究KMP算法，看来很多版本，有不同的语言写的，但是感觉越看越乱，最后自己试着写一份进行总结
首先，KMP算法使字符串匹配中的优化算法，使原来的O（m*n）降到了O(m+n)
关于他的理解，我推荐先看视频，他讲的很清楚了。汪都能听懂的KMP字符串匹配算法
然后从可视化方面理解，推荐看看如何更好的理解和掌握 KMP 算法? – 佑子的回答 – 知乎容
最后从代码层理解Searching for Patterns | Set 2 (KMP Algorithm)
代码不要看太多别人的，我感觉好多人写的也有问题，我在自己运行处问题时，有看有些同学写的，被带到其他坑里了。。。
最后记录代码
'''先求next数组'''def next_list(pattern): next=[] pattern_list=list(pattern) j=0 i=1 for s in range(len(pattern)): #第一位一直是0 if s==0: next.append(0) #看第i个和第j个字母是否相同，如果相同，则累加 #同时i,j同时右移 elif(pattern_list[i]==pattern_list[j]): next.append(j+1) j+=1 i+=1 #如果不相同，则next为0，同时j也退回第一个位置，i继续前进一个位置 else: next.append(0) j=0 i=s+1 print(next) return nextnext_list('ABABCABAB') def kmp(text,pattern): #text的位置 i=0 #pattern的位置 j=0 next=next_list(pattern) if(not(text and pattern)): print('字符串为空，请输入字符串') elif(len(text)<len(pattern)): print('原字符串过小') elif(text==pattern): print('字符串一致') else: while( (i<len(text) )): print((text[i],pattern[j])) print(i,j) #如果相同，则进行下一个对比 if( text[i]==pattern[j]): i+=1 j+=1 #判断是不是匹配完了 if j==len(pattern): print('从第{0}个位置开始匹配'.format(i-j)) j=next[j-1] #如果不匹配，则j反回到前一个字母对应的next elif i<len(text) and text[i]!=pattern[j]: #我就是少了这个判断，一直有问题，就是在不匹配后的第二步，后面这个很关键 if j!=0: #这个就是精髓了，如果不匹配，就去找第一个和这个匹配的字符串，然后在这个前面的匹配字符串 #的后一个字母拿出来，再与长text比较的第i个字母比较 j=next[j-1] #如果j已经回到了0，则通过增加i,text移动到下一个字母 else: i+=1# text = "ABABDABACDABABCABAB"# pattern = "ABABCABAB" text='abxabcabcaby'pattern='abcaby'kmp(text,pattern)#output:next=[0, 0, 0, 1, 2, 0]('a', &<strong style="color:transparent">本文来源gaodai#ma#com搞@@代~&码*网/</strong>#39;a')0 0('b', 'b')1 1('x', 'a')2 0('a', 'a')3 0('b', 'b')4 1('c', 'c')5 2('a', 'a')6 3('b', 'b')7 4('c', 'c')8 2('a', 'a')9 3('b', 'b')10 4('y', 'y')11 5从第6个位置开始匹配
相关推荐：
KMP算法最浅显理解
kmp算法详解
KMP算法中最难理解的地方的理解
kmp算法原理及实现
图解KMP算法
以上就是Python实现字符串的KMP算法的详细内容，更多请关注搞代码gaodaima其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：Python实现字符串的KMP算法
转载请注明原文链接：Python实现字符串的KMP算法
