KMP algorithm – looks for the position in the text string where the pattern string first appears

In computer science, the Knuth-Morris-Pratt string lookup algorithm (abbreviated as the KMP algorithm) looks for the occurrence of a word W in a string S (or the number of occurrences of W in S). The algorithm takes advantage of the fact that a word when mismatched contains enough information on its own to determine where the next match is likely to start to avoid rechecking previously matched characters.

// 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
    } else if text == "" {
        return - 1
    }
    // text ! = "" && pattern ! = ""
    var (
        tl = len(text)
        pl = len(pattern)
    )
    if tl < pl {
        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