Python实现字符串的KMP算法

'''
先求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个位置开始匹配