【经典问题】字符串匹配

1、BF算法

BF（Brute Force）算法就是朴素的暴力匹配。BF算法的基本思想是从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已比较成功，则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的子串，则匹配失败。

def BF(s, p):
    '''
   Brute-Force算法实现字符串匹配
    '''
    indies = []
    n = len(s)
    m = len(p)
    for i in range(n - m + 1):
        index = i  
        for j in range(m): 
            if s[index] == p[j]: 
                index += 1
            else: 
                break
        if index - i == m: 
            indies.append(i) 
        
    return indies

print(BF('abcxabcdabcdabcy','abcdabcy'))

2、KMP算法

KMP（Knuth-Morris-Pratt）算法是对BF算法的改进，差别在于KMP算法在出现字符串不相等的情况时，不需要返回到字串的开头重新比较。具体过程就是计算一张部分匹配表来改进移动距离。

def getNextList(s):
    n = len(s)
    nextList = [0, 0]
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = nextList[j]
        if s[i] == s[j]:
            j += 1
        nextList.append(j)
    return nextList

def KMP(s, p):
    '''
    Knuth-Morris-Pratt算法实现字符串匹配
    '''
    n = len(s)
    m = len(p)
    nextList = getNextList(p)
    indies = []
    j = 0
    for i in range(n):
        while s[i] != p[j] and j > 0:
            j = nextList[j]

        if s[i] == p[j]:
            j += 1
            if j == m:
                indies.append(i-m+1)
                j = nextList[j]
    return indies

print(KMP('abcxabcdabcdabcy','abcdabcy'))

3、BM算法

BM（Boyer-Moore）算法是对KMP进一步的改进。总体来说BM算法效率是高于KMP算法的，文本量越大BM算法的效果越明显。BM算法通过两张表来改进移动的距离。

def getBMBC(pattern):
    # 预生成坏字符表
    BMBC = dict()
    for i in range(len(pattern) - 1):
        char = pattern[i]
        # 记录坏字符最右位置（不包括模式串最右侧字符）
        BMBC[char] = i + 1
    return BMBC

def getBMGS(pattern):
    # 预生成好后缀表
    BMGS = dict()

    # 无后缀仅根据坏字移位符规则
    BMGS[''] = 0

    for i in range(len(pattern)):

        # 好后缀
        GS = pattern[len(pattern) - i - 1:]

        for j in range(len(pattern) - i - 1):

            # 匹配部分
            NGS = pattern[j:j + i + 1]

            # 记录模式串中好后缀最靠右位置（除结尾处）
            if GS == NGS:
                BMGS[GS] = len(pattern) - j - i - 1
    return BMGS

def BM(string, pattern):
    '''
    Boyer-Moore算法实现字符串查找
    '''
    m = len(pattern)
    n = len(string)
    i = 0
    j = m
    indies = []
    BMBC = getBMBC(pattern=pattern)  # 坏字符表
    BMGS = getBMGS(pattern=pattern)  # 好后缀表
    while i < n:
        while (j > 0):
            if i + j -1 >= n: # 当无法继续向下搜索就返回值
                return indies

            # 主串判断匹配部分
            a = string[i + j - 1:i + m]

            # 模式串判断匹配部分
            b = pattern[j - 1:]

            # 当前位匹配成功则继续匹配
            if a == b:
                j = j - 1

            # 当前位匹配失败根据规则移位
            else:
                i = i + max(BMGS.setdefault(b[1:], m), j - BMBC.setdefault(string[i + j - 1], 0))
                j = m

            # 匹配成功返回匹配位置
            if j == 0:
                indies.append(i)
                i += 1
                j = len(pattern)

print(BM('abcxabcdabcdabcy','abcdabcy'))