Leetcode 28. 实现 strStr()

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def kmp_nextval(needle):
            nextval=[]
            i,j=0,-1
            nextval.append(j)
            while len(nextval)<len(needle):
                if j==-1 or needle[i]==needle[j]:
                    i,j=i+1,j+1
                    nextval.append(nextval[j] if needle[i]==needle[j] else j)
                else:
                    j=nextval[j]
            return nextval
        nextval=kmp_nextval(needle)
        i,j=0,0
        while j<len(needle) and i<len(haystack):
            if j==-1 or haystack[i]==needle[j]:
                i,j=i+1,j+1
            else:
                j=nextval[j]
        if j==len(needle):
            return i-j
        else:
            return -1                

Leetcode 28. 实现 strStr()

原文：https://www.cnblogs.com/ximelon/p/11982212.html