假设有两个字符串：t(目标串，长度n)和p(模式串，长度m)，通常m<<n。
朴素串匹配算法
- 优点
简单易懂 - 缺点
效率低
时间复杂度分析：最坏的情况是每一趟都在模式串的最后遇到不匹配，那么每一趟比较的次数是n-m+1, 总的比较次数是 mx(n-m+1), 因为m<<n, 所以时间复杂度为O(mxn)
代码实现：
def naive_match(t,p):
m, n = len(p), len(t)
i, j = 0, 0
while i < m and j < n:
if p[i] == t[j]:
i, j = i+1, j+1
else: #字符不匹配，考虑t串的下一个位置
i, j = 0, j-i+1 # j-i+1为相对位置加1
if i == m: # p串完全匹配后（i++）i的值变为m
return j-i #此时j的值减去p串的长度（i或者m）就是所在下标
return 'No Match!' #无匹配则返回'No Match'
#实例化
t = ' abc de'
p = 'de'
print naive_match(t, p)
#输出 6
#换一种想法去实现
def naive_match1(p,t):
m, n, i = len(p), len(t), 0
for i in range(n-m+1):
if t[i:i+n-1] == p:
return i
return 'No match!'
p = 'abc'
t = 'abdabc'
print naive_match1(p,t)
KMP算法（无回溯串匹配算法）
分析：算法的关键在于构建一个跳转表(pnext表)，当第i个字符匹配失败时不是重新从头开始匹配（例如朴素串匹配算法），而是通过构建好的跳转表跳转到第j个字符。例如：
0 1 2 3 4 5 6 7 # 字符串的位置
a b c a b c d a # p串
0 0 0 0 1 2 3 0 # pnext表，如果匹配不成功 跳转的位置
解释：当第6位的字符d匹配失败后可以直接跳转到第3位的a， 因为它们之前的abc是相同的，不需要再匹配一遍了。
更近一步分析：如果p串i位置与t串的j位置匹配失败了，先去查找p串i位置之前的从0开始的串（假设[0,k], k<i）与t串j位置之前的串（[j-k,j]）是否有相同的片段，如果有找出那个k值，若木有则按照朴素匹配算法进行。
移动的位数 = 已匹配的字符数 - 对应的部分匹配值（查表）
如何得到p串每个字符的部分匹配值（如何生成next表）？
对于每个p串的字符，前缀与后缀共有字符的个数就是该字符的部分匹配值。 详细解释
那么如何构造部分匹配表（next表）呢，python代码如下：
Next表 （部分匹配表，跳转表）
def partial_table(p):
prefix = set() #集合
postfix = set()
ret = [0] #存放p串匹配值，因为第一个字符的匹配值肯定为0，先把0存进去
for i in range(1,len(p)): #从第二个字符开始
#获取前i+1个字符串的前缀（例如对于abc，前缀有a,ab）
#Note:切片[0:3]-->索引0,1,2（第一个索引是0可以省略-->[:3]-->取前三个数）
#Note:range函数也一样取不到后面的数-->rang(1,3)-->>1,2
prefix.add(p[:i]) #因为对于不同的字符前缀都有相同的部分，这里只需要添加就行了
#获取前i+1个字符串的后缀(例如对于abc，后缀有bc,c)
postfix = {p[j:i+1] for j in range(1,i+1)} #对于不同的字符后缀总是不一样
ret.append(len(prefix&postfix))
return ret
KMP算法实现
#-*-coding=utf-8-*-
#KMP
def kmp_match(t, p):
m,n = len(t),len(p)
cur = 0 #起始指针cur
table = partial_table(p)
while cur <= m-n: #最多做m-n趟匹配
for i in range(n): #在每一趟比较中
if s[i+cur]!=p[i]: #匹配不成功时
cur += max(i - table[i-1], 1) #移动的位数 = 以匹配的字符数 - 匹配值
break
else:
return True
return False
# 测试
p = 'ABCDABD'
s = 'BBC ABCDAB ABCDABCDABDE'
print partial_table(p)
print kmp_match(s, p)
网友评论