数据结构字符串模式匹配问题 KMP算法

发布网友发布时间：2022-04-25 03:17

共3个回答

懂视网时间：2022-04-18 18:45

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

数据结构 字符串 模式匹配问题 KMP算法

数据结构字符串模式匹配问题 KMP算法