golang刷leetcode 经典（8） kmp 实现strstr（）

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:


输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:

func strStr(haystack string, needle string) int {
     if haystack==needle || needle==""{
         return 0
     }
     if len(needle)==0{
        return -1
    }
    next:=getNext(needle)
    m:=0
    for i:=0;i<len(haystack);i++{
        for m>0 && haystack[i]!=needle[m]{
            m=next[m-1]
        }
        if haystack[i]==needle[m]{
            m++
            if m==len(needle){
                return i-m+1
            }
        }
    }
    return -1
}

func getNext(needle string)[]int{
    next:=make([]int,len(needle))
    i:=0
    for j:=1;j<len(needle);j++{
        for i>0 && needle[i]!=needle[j]{
          i=next[i-1]
        }
        if needle[j]==needle[i]{
            i++
        }
        next[j]=i
    }
    return next
}