golang-KMP算法

import (
    "fmt"
)
func KMP(haystack, needle string) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }
    pi := substringRepetition(needle)
    for i, j := 0, 0; i < n; i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = pi[j-1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1

}

func substringRepetition(needle string) []int {
    m := len(needle)
    pi := make([]int, m)
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && needle[i] != needle[j] {
            j = pi[j-1]  //一眼能看明白这个的~，请允许我称呼你一声大神
        }
        if needle[i] == needle[j] {
            j++
        }
        pi[i] = j
    }
    return pi
}