Rumah >pembangunan bahagian belakang >Tutorial Python >Python实现字符串的KMP算法
本文实例讲述了Python实现字符串的KMP算法。分享给大家供大家参考，具体如下：
今天研究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 next
next_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', '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个位置开始匹配
相关推荐：
Atas ialah kandungan terperinci Python实现字符串的KMP算法. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!