KMP算法

    # KMP算法
    def KMP(self, haystack: str, needle: str) -> int:

        # 计算next数组
        ne = [0] * len(needle)
        if len(needle) > 0:
            ne[0] = -1

        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                j += 1
                ne[i] = j
                i += 1
            elif j > 0:
                j = ne[j]
            else:
                ne[i] = 0
                i += 1

        # 匹配
        i = j = 0
        while i < len(haystack) and j < len(needle):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif ne[j] == -1:
                i += 1
            else:
                j = ne[j]
        return i - j if j == len(needle) else -1