gpt4 book ai didi

python3 kmp 字符串匹配的方法

转载 作者:qq735679552 更新时间:2022-09-27 22:32:09 24 4
gpt4 key购买 nike

CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python3 kmp 字符串匹配的方法由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.

先声明,本人菜鸟一个,写博客是为了记录学习的过程,以及自己的理解和心得,可能有的地方写的不好,希望大神指出。。.

抛出问题 。

给定一个文本串test_str(被匹配的字符串)和模式串pat_str(需要从文本串中匹配的字符串),从文本串test_str中找出模式串pat_str第一次出现的位置,没有的话返回 -1 。

暴力方式 。

在说kmp之前,我们先来讲下“暴力方式“,也就是说我们最原始的方法。  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
text_str = 'asdabcdace'
pat_str = 'abcdace'
 
def str_match(text_str,pat_str):
   for i in range ( 0 , len (text_str)):
     j = 1
     while j < len (pat_str):
       if text_str[i:i + j] ! = pat_str[ 0 :j]: #从text_str第i个字符开始,看匹配是否成功
         break  #匹配失败,直接跳出循环,i+1,继续从第一个字符匹配
       j + = 1   #匹配成功就继续匹配下一个字符,知道pat_str每个字符都匹配完
     if j = = len (pat_str):
       return i
   return - 1
 
print (str_match(text_str,pat_str))

之所以称之为暴力解法,就是因为每次匹配失败之后就将模式串,向后移动一位,从头开始匹配,一直循环下去。造成时间复杂度高,kmp也就是优化这个地方,每一次匹配失败,下次移动的距离next值 。

python3 kmp 字符串匹配的方法

kmp 。

如果让我完全给你讲懂kmp算法可能不太容易,我只能大致粗略的将下它的一步步实现。我认为就一个重点, 。

如何求出模式串每个字符对应的next值 。

因为可能,每一次匹配失败的长度的字符不一样,也就对应每次移动的距离不一样,那我们如何求每个字符对应的next值,这就引出了另一个概念 。

最大前缀和最大后缀 。

    python3 kmp 字符串匹配的方法

假定最大前缀=最大后缀,长度为k 那么第i位字符,对应的next值就为k+1,一次循环就能求出每个字符的next值 。

代码实现   。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#求字符串的next值
text_str = 'asdabcdace'
pat_str = 'abcdace'
 
#得到字符对应的next值
def str_next(s):
   #前两个字符默认等于1
   next = [ 1 , 1 ]
   for x in range ( 2 , len (s)):
     next .append(str_max_prx(s,x, next [x - 1 ] - 1 ) + 1 )
   return next
#参数 s字符串,匹配进行到的位置,下次开始匹配的位置
def str_max_prx(s,x,last_value):
   next = 0
   for i in range (last_value,x):
     if s[ 0 :i] = = s[x - i:x]:
       next = i
   return next
def str_match(s,m):
   next = str_next(s)
   i = 0
   s_len = len (s)
   m_len = len (m)
   while i < = m_len:
     flag = true   #标志位,用来判断是否匹配成功
     index = 1
     while index < = s_len:
       if m[i:i + index] ! = s[ 0 :index]:
         i = i + next [index]
         flag = false
         break
       else :
         index + = 1
     if flag:
       break
   if i > = m_len:
     i = - 1
   return i
res = str_match(pat_str,text_str)
print (res)

代码就是这样,很多东西可能还需要自己理解。我记个笔记,为之后方便查找,希望对你能有帮助。也希望大家多多支持我.

原文链接:http://www.cnblogs.com/7749ha/p/9016246.html 。

最后此篇关于python3 kmp 字符串匹配的方法的文章就讲到这里了,如果你想了解更多关于python3 kmp 字符串匹配的方法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com