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