字符串匹配的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算法

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

以上代码参考http://cnblogs.com/goodspeed/p/3295456.html

另外，还有BM算法，sunday算法以及horspool算法，后两种是迁移中的变种，“BM算法在实际应用中比KMP算法*到五倍”。

秒客网

字符串匹配的python实现

相关文章