算法总结-字符串匹配

def brute_force_match(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n-m+1):
        j = 0
        while j < m and text[i+j] == pattern[j]:
            j += 1
        if j == m:  # a match
            return i
    return -1   

# 一个例子，模式串"abababca"：
#     index   0   1   2   3   4   5   6   7
#     char    a   b   a   b   a   b   c   a
#     PMT     0   0   1   2   3   4   0   1
#     next   -1   0   0   1   2   3   4   0   1

# 预处理阶段：
# 首先PMT数组的长度和模式串的长度相同，对于上例。
#     index=0，串 a     前缀集合{}，后缀集合{}，交集为{}，故PMT[0] = 0
#     index=1, 串 ab    前缀集合{a}，后缀集合{b}, 交集为{}，故PMT[1] = 0
#     index=2, 串 aba   前缀集合{a, ab}, 后缀集合{b, ba}, 交集为{a}, 故PMT[1] = 0
#                         ······
#     index=7, 串 abababca 前缀集合后缀集合交集为{a}, PMT[7] = 1
 
# 匹配阶段：
# 然后有了PMT数组之后，我们就能进行匹配过程，如对文本串"ababababca"，
#    a     b    _a_   _b_   _a_   _b_   [a]   b   c   a     i = 6
#   _a_   _b_   _a_   _b_    a     b    [c]   a             j = 6
# 当i=6, j=6是第一次出现失配（中括号对应得字符不相同），而这是[i-j, i-1]与[0, j-1]是
# 已经匹配过的完全相同得子串部分，而这一模式串得子串pattern[:j] = "ababab" 中有相同的
# 前后缀abab，长度为PMT[j-1] = 4, 对应就是上面下划线包围部分的字符是对应匹配的，不需要
# 再重复比较。直接将pattern串移动到PMT[j-1]与i进行匹配即可（i不需要移动）。

def KMP_match(text, pattern):

    def cal_next(p):
        """预处理，计算next数组"""
        next = [0] * (len(p) + 1) # 注意next数组长度是m+1
        next[0] = -1
        # 初始化i=1,j=-1这样从模式串(i=1, j=0)开始匹配（会执行一遍i++,j++）
        # 即保证前缀p[0, m-2] 和 后缀p[1:m-1] 匹配
        i, j = 0, -1
        
        while i < len(p):
            # -1的作用：
            #   1. 实现前缀与后缀匹配
            #   2. 出现失配i移动到i+1, j移动到0
            if j == -1 or p[i] == p[j]: 
                i += 1                  
                j += 1
                next[i] = j
            else:
                j = next[j]
        return next

    def kmp(text, p):
        """匹配过程"""
        i = j = 0
        next = cal_next(p)
        while i < len(text) and j < len(p):
            if j == -1 or text[i] == p[j]:  # -1的作用，如果出现了-1，就是next[0],
                i += 1                      # 说明模式串第一字符就不匹配，i和j都右移一位
                j += 1                      # i移动到了i+1,  j+1移动到了0，即从头开始
            else:
                j = next[j]
        if j == len(p):  # a match
            return i - j
        return -1

    return kmp(text, pattern)

text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"

def pre_bad_ch(p):
    """坏字符"""
    m = len(p)
    bmbc = [m] * 128  # 初始化为m, 没出现的字符移动整个串的长度
    # 出现的移动长度为m - 1 - k(k到字符串尾的长度), 从左到右循环，后面出现
    # 的会覆盖前面出现的值，最终保留下来就是最右边出现的对应移动值。
    for k in range(m - 1):
        bmbc[ord(p[k])] = m - 1 - k
    return bmbc

def pre_good_suffix(p, suff):
    m = len(p)
    # 依然初始化为m。
    # 处理上述 情况3. 没有与后缀相同的子串或者前缀
    bmgs = [m] * m  
    
    # 对于 情况2. 有前缀和好后缀一致，即：p[m-s:m] == p[0, s]，
    # 我们可以将这个前缀视为已匹配的部分，将模式串移到这个前缀与好后缀的后面对齐的位置。
    j = 0
    for k in range(m - 1, -1, -1):
        if suff[k] == k + 1:  # 与后缀相同的长度k+1说明是模式串的一个前缀
            while j < m - 1 - k:
                # 移动字符的个数是前缀的位置（用k表示）字符串尾部的长度(m-1 - k)。
                # TODO：这里我看好多代码都加了一个判断bmgs[j]==m，比如参考文献[4],
                #   可是我觉得好没有必要
                bmgs[j] = m - 1 - k
                j += 1
    
    # 情况1，有子串与好后缀一致。对应j=m-1-suff[k]
    for k in range(m - 2 + 1):
        j = m - 1 - suff[k]
        bmgs[j] = m - 1 - k
    return bmgs

def suffix_brute_force(pattern):
    m = len(pattern)
    suff = [0] * m
    suff[m - 1] = m
    for i in range(m - 2, -1, -1):
        j = i
        while j >= 0 and pattern[j] == pattern[m - 1 - i + j]:
            j -= 1
        suff[i] = i - j
    return suff

def suffix(pattern):
    m = len(pattern)
    suff = [0] * m
    suff[m - 1] = m
    f, j = 0, m-1
    for i in range(m - 2, -1, -1):
        if i > j and suff[i + m - 1 - f] < i - j:
            suff[i] = suff[i + m - 1 - f]
        else:
            # j = min(j, i)
            if i < j:
                j = i
            f = i
            while j >= 0 and pattern[j] == pattern[j + m - 1 - f]:
                j -= 1
            suff[i] = f - j
    return suff

def BM_match(text, pattern):
    n, m = len(text), len(pattern)
    bmbc = pre_bad_ch(pattern)
    bmgs = pre_good_suffix(pattern)
    print('bc', bmbc[ord('a'):])
    print('gs', bmgs)
    j = 0
    while j <= n - m:
        i = m - 1
        while i >= 0 and pattern[i] == text[i + j]:
            i -= 1
        if i < 0: # 一个完整的match, 多次匹配可以记下结果并j += bmgs[0]
            return j
        else:
            # BM算法的核心,每次从两种思想中移动距离长的一个
            j += max(bmbc[ord(text[i + j])] - m + 1 + i, bmgs[i])
    return -1

def match(text, pattern):
    def check(s, t):
        if len(s) != len(t):
            return False
        for i in range(len(s)):
            if s[i] != t[i]:
                return False
        return True

    n, m = len(text), len(pattern)
    if n < m:
        return -1
    if m == 0:
        return 0

    MOD = int(1e9+7)
    p = 113
    h = p ** (m - 1) % MOD
    code = lambda c: ord(c) - ord('a')
    
    target = cur_val = 0
    for i in range(m):
        target = (target * p + code(pattern[i])) % MOD
        cur_val = (cur_val * p + code(text[i])) % MOD

    if cur_val == target and check(text[:m], pattern):
        return 0

    for i in range(m, n):
        cur_val = ( (cur_val - code(text[i-m]) * h) * p + code(text[i])) % MOD
        # hash值相同，检查串是否相同
        if cur_val == target:
            if check(pattern,text[i - m + 1:i + 1]):
                return i - m + 1
    return -1