PHP8.1.21版本已发布
vue8.1.21版本已发布
jquery8.1.21版本已发布

飘逸的python

黄舟
黄舟 原创
2016-12-21 17:27:09 1242浏览

首先我们来看一下字符串的朴素匹配.

可以想象成把文本串s固定住,模式串p从s最左边开始对齐,如果对齐的部分完全一样,则匹配成功,失败则将模式串p整体往右移1位,继续检查对齐部分,如此反复.


#朴素匹配
def naive_match(s, p):
   m = len(s); n = len(p)
   for i in range(m-n+1):#起始指针i
       if s[i:i+n] == p:
           return True
   return False

关于kmp算法,讲的最好的当属阮一峰的<字符串匹配的KMP算法>.一路读下来,豁然开朗.
其实就是,对模式串p进行预处理,得到前后缀的部分匹配表,使得我们可以借助已知信息,算出可以右移多少位.即 kmp = 朴素匹配 + 移动多位.
更多细节请看阮一峰的文章,这里就不展开了.
下面给出python的代码实现.



#KMP
def kmp_match(s, p):
   m = len(s); n = len(p)
   cur = 0#起始指针cur
   table = partial_table(p)
   while cur<=m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
break
else:
return True
return False

#部分匹配表
def partial_table(p):
'''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
   prefix = set()
   postfix = set()
   ret = [0]
   for i in range(1,len(p)):
       prefix.add(p[:i])
       postfix = {p[j:i+1] for j in range(1,i+1)}
       ret.append(len((prefix&postfix or {''}).pop()))
   return ret

print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print partial_table("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")

 以上就是飘逸的python的内容,更多相关内容请关注PHP中文网(m.sbmmt.com)! 


声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。