字符串匹配算法：KMP

Knuth–Morris–Pratt（KMP）是由三位数学家克努斯、莫里斯、普拉特同时发现，所有人们用三个人的名字来称呼这种算法，KMP是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n)

字符匹配：给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1

在介绍KMP算法之前，我们先看一下另一种暴力算法（BF算法）去解字符匹配应该怎么做

 BF算法：时间复杂度O(m*n)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        #hi是haystack的当前索引
        hi = 0
        haystackLength = len(haystack)
        needleLength = len(needle)
        for i in range(haystackLength - needleLength+1):
            #每次匹配等于和完整的needle的字符串逐一匹配
            if haystack[i:i+needleLength] == needle:
                return i
        return -1