go indexOf

indexOf

indexOf(s, p string) 函数会返回p在s中首次出现的位置，倘如没有则返回-1，本次使用之前提到过的kmp算法来作为indexOf的核心，并用来解决leetcode28题

code

func strStr(haystack string, needle string) int {

    return indexOf(haystack, needle)
}

func indexOf(s, p string) int {
    if len(p) == 0 {
        return 0
    }
    next := make([]int, len(p))
    next[0] = -1

    j := -1
    for i := 1; i < len(p); i++ {
        for j != -1 && p[i] != p[j+1] {
            j = next[j]
        }
        if p[i] == p[j+1] {
            j++
        }
        next[i] = j
    }

    j = -1
    for i := 0; i < len(s); i++ {
        for j != -1 && s[i] != p[j+1] {
            j = next[j]
        }
        if s[i] == p[j+1] {
            j++
        }

        if j == len(p) - 1 {
            return i - j
        }
    }
    return -1
}