KMP算法

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle == '':
            return 0
        m = len(haystack)
        n = len(needle)
        if n > m:
            return -1
        prefix = self.get_prefix(needle)
        i = 0
        j = 0
        while i < m:
            # 匹配上的情况下i,j各加一
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                if j == n:
                    return i - j
            else:
                # 不匹配的情况下，j发生变化，利用prefix
                j = prefix[j]
                # 变化之后判断j是否为-1,若为-1,j从0开始,i移动到下一位
                if j == -1:
                    j = 0
                    i += 1
        return -1

    def get_prefix(self, p):
        n = len(p)
        prefix = [0] * n
        l = 0
        i = 1
        while i < n:
            if p[i] == p[l]: # 相等
                l += 1
                prefix[i] = l
                i += 1
            else: # 不相等
                if l > 0: # l > 0
                    l = prefix[l-1]
                else: # l < 0
                    prefix[i] = 0
                    i += 1
        # 头部加-1,删掉最后一个元素
        prefix = [-1] + prefix[:-1]
        return prefix
```

- 参考资料: 
[灯笼哥](https://www.bilibili.com/video/BV1Px411z7Yo/?spm_id_from=333.788.recommend_more_video.0)