图片无法上传

详细解析请移步b站专栏： k m p

class Solution(object):
    def strStr_0(self,haystack,needle):
    # 暴力搜素
        n=len(haystack)
        m=len(needle)
        if n==0:return 0
        if n<m:return -1
        for i1 in range(n):
            if haystack[i1]!=needle[0]:continue
            for i2 in range(m):
                if i1+i2==n:return -1
                if haystack[i1+i2]!=needle[i2]:break
            else:return i1
        return -1

    def strStr_1(self,haystack,needle):
    # KMP 算法
        n=len(haystack)
        m=len(needle)

        if n<m:return -1
        if not n:return n
        if not m:return m

        def getTable(string):
            s=len(string)
            memory=[0]*s
            i=1
            l=0
            while i<s:
                if string[i]==string[l]:
                    l+=1
                    memory[i]=l
                    i+=1
                else:
                    if l==0:
                        i+=1
                    else:
                        l=memory[l-1]            
            result=[None]+memory[:-1]
            return result

        prefixTable=getTable(needle)
        i1=i2=0
        while i1<n:
            if i2==m-1 and haystack[i1]==needle[i2]:
                return i1-m+1
            if haystack[i1]==needle[i2]:
                i1+=1
                i2+=1
            else:
                i2=prefixTable[i2]
                if i2==None:
                    i1+=1
                    i2=0
        return -1

if __name__=='__main__':

    haystack="ccaaaaabaaabaaac"

    needle  ="aaaaabaaab"

    haystack="aabaaabaaac"

    needle="aabaaac"

    sl=Solution()

    print(sl.strStr_0(haystack,needle))

    print(sl.strStr_1(haystack,needle))