算法实现过程

ADL

算法代码实现

求模式串的失败函数（next数组）

入参：模式串
pat='ababc'

def Fail(pat):
    """
    求模式串的失败函数（next数组）
    :param p: 模式串
    :return: next数组
    """
    if pat is None:
        return None
    next = []
    """next第一个是-1，第二个是0"""
    next.append(-1)
    next.append(0)
    
    for i in range(2, len(pat)):
        str = pat[0:i]      # 模式串子串
        count = 1
        next_num = 0
        for j in range(len(str) - 1, 0, -1):
            """前缀与后缀"""
            pri = str[0:count]
            last = str[j:len(str)]
            if pri == last:
                next_num = len(pri)
            count += 1
        next.append(next_num)
    return next

返回值：[-1, 0, 0, 1, 2]

KMP算法实现

入参：目标串，模式串
s = 'abaababcaa'
pat = 'ababc'

def KMP(s, pat):
    """
    KMP算法
    :param s:
    :param pat:
    :return:
    """
    next = Fail(pat)    # 求出模式串的失败函数
    i = 0   # 模式串指针
    j = 0   # 目标串指针（不后退）
    while j < len(s) and i < len(pat):
        """循环条件结束的条件"""
        if s[j] == pat[i]:
            """字符匹配，指针后移"""
            j += 1
            i += 1
        else:
            """字符不匹配"""
            if i == 0:
                """
                如果第一个字符就匹配失败，j直接后移
                根据next数组找到的下一位与当前目标串字符不匹配
                """
                j += 1
            else:
                """
                不匹配时，查找next数组
                i指针的前一个next数组值+1
                """
                i = next[i-1]+1
    if i < len(pat):
        """i指针没有指到模式串的末尾"""
        return '查找失败'
    return j-len(pat)

返回值：3