Leetcode 28. Implement strStr()

Topic link

Problem Solving using KMP algorithm (submitted and approved)

func strStr(haystack string, needle string) int {
    return firstIndex(haystack, needle)
}

// Find the index of the first occurrence of Pattern in text. If not, return -1.
// Convention: Return 0 as long as pattern is an empty string
func firstIndex(text, pattern string) int {
    if pattern == "" {
        return 0
    }
    if text == "" {
        return - 1
    }
    // text ! = "" && pattern ! = ""
    if len(text) < len(pattern) {
        return - 1
    }
    // tl >= pl
    return indexKMP(text, pattern)
}

func indexKMP(text, pattern string) int {
    var (
        ti int
        pi int
        tl = len(text)
        pl = len(pattern)
        next = getNextArray(pattern)
    )
    for ti < tl {
        if text[ti] == pattern[pi] {
            ti++
            pi++
            if pi == pl {
                return ti-pl
            }
        } else if pi == 0 {
            ti++
            if tl-ti < pl {
                break}}else {
            pi = next[pi- 1]
            if tl-ti < pl-pi {
                break}}}return - 1
}

func getNextArray(p string) []int {
    // Preconditions: p is not an empty string
    if p == "" {
        panic("p is empty")}var (
        j    int // Prefix the current index
        i    = 1 // suffix current index
        l    = len(p)
        next = make([]int, l)
    )
    // next[0] = 0, implicit initialization
    for i < l {
        if p[j] == p[i] {
            j++
            next[i] = j
            i++
        } else if j == 0 {
            next[i] = 0
            i++
        } else {
            j = next[j- 1]}}return next
}
Copy the code