一、描述

二、题解

#KMP算法（$O(N+M)$）

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        tat_len = len(haystack)
        patt_len = len(needle)
        if patt_len == 0:
            return 0
        # create next array
        i = 1
        k = 0
        next_ = [0]*patt_len
        while(i<patt_len):
            if(needle[i] == needle[k]):
                next_[i] = k+1
                k+=1
                i+=1
            else:
                if k==0:
                    next_[i] = 0
                    i+=1
                else:
                    k = next_[k-1]
        # matching
        i = 0
        j = 0
        while(i<tat_len):
            while(j<patt_len and i<tat_len and haystack[i]==needle[j]):
                i+=1
                j+=1
            if j== patt_len: # 匹配完成
                return i-j
            else:
                if j>0: # 匹配个数大于0
                    j = next_[j-1]
                else: # 开始就没匹配上
                    i+=1
        return -1

如有问题或建议欢迎私信。
严禁私自转载，侵权必究
参考：
[1] 【经典算法】——KMP，深入讲解next数组的求解 [博客园]
[2] 很详尽KMP算法（厉害）[博客园]