Python字符串匹配

假设有两个字符串：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)