字符串匹配的python实现
所有字符串匹配算法的核⼼问题是，当出现不匹配时，如何向后移动模式串
⼀、暴⼒匹配算法
如果要匹配⼀个字符串s 和⼀个模式串p，则从i=0开始依次匹配s[i:(i+len(p))]，简单粗暴，代码如下：
def matcher(t, p):
# param t: the string to check
# param p: pattern
n = len(t)
m = len(p)
for i in xrange(0, n-m+1):
if p == t[i:i+m]: return True
⼆、KMP算法
参见：blog.csdn/v_july_v/article/details/7041827
简单来说，就是当匹配字符串s和模式串p时，当s[i]和p[j]不匹配时，不回溯S，⽽是将p右移⼀定位数开始匹配。所右移位数由以下规则确定：若p[j]前⾯的字符串最⼤长度的前后缀相同的字符串长度为L, 则右移（已匹配字符串长度—L），⽂字描述⽐较抽象，参见上⾯博客内容def pmt(s):
"""
PartialMatchTable
"""
prefix = [s[:i+1] for i in range(len(s)-1)]
postfix = [s[i+1]: for i in range(len(s)-1)]
intersection = list(set(prefix) & set(postfix))    # 得到相同前后缀
if intersection:
return len(intersection[0])    # 得到最长前后缀
return o
正则匹配哈希值
def kmp(t, p):
# t: the string to check
# p: pattern
i = 0
while i < len(t) - len(p) + 1:
match = True
for j in range(len(p)):
if t[i+j] != p[j]:
match = False
break
if match:
return True
# kmp
if j:
i += j - pmt(p[:j])
else: i += 1
return False
以上代码参考cnblogs/goodspeed/p/3295456.html
另外，还有BM算法，sunday算法以及horspool算法，后两种是迁移中的变种，“BM算法在实际应⽤中⽐KMP算法到五倍”。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。