KMP算法

def kmp_match(target, part):
    """ kmp算法 """

    def create_next():
        """ 构建next数组 
            create_next('ABCDABD') = [0, 0, 0, 0, 1, 2, 0]
        """
        # 生成前缀
        prefix = {part[:i] for i in range(1, len(part))}
        postfix = {}
        _ = [0]
        # 生成next数组
        for i in range(1, len(part)):
            # 生成每个子串的后缀
            # 'ABCDABD'
            # {'B'}
            # {'BC', 'C'}
            # {'CD', 'BCD', 'D'}
            # {'BCDA', 'CDA', 'A', 'DA'}
            # {'DAB', 'BCDAB', 'AB', 'CDAB', 'B'}
            # {'BCDABD', 'BD', 'D', 'ABD', 'CDABD', 'DABD'}
            postfix = {part[j:i + 1] for j in range(1, i + 1)}
            # 计算并向next_list添加每一位的适配度
            _.append(len((prefix & postfix or {''}).pop()))
        return _

    target_len = len(target)
    part_len = len(part)
    next_list = create_next()
    cur = 0
    # 即便一位一位右移，最坏的情况有 target_len - part_len 次需要右移
    while cur <= target_len - part_len:
        # 匹配子串
        for i in range(part_len):
            if target[i + cur] != part[i]:
                # 出现了不匹配的坏字符，则进行右移
                # 移动位数 = 已匹配的字串长度 - 字符匹配度
                # 最少像右移动一位
                cur += max(i - next_list[i - 1], 1)
                break
        else:
            return cur
    return -1

if __name__ == '__main__':
    a = kmp_match('fergdvwertergasfwqerfdsf', 'terg')
    print(a) # 输出为9