字符串匹配的python实现

浏览数：43 / 时间：2015年06月08日

所有字符串匹配算法的核心问题是，当出现不匹配时，如何向后移动模式串

一、暴力匹配算法

如果要匹配一个字符串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算法

参见：http://blog.csdn.net/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