How do I implement KMP string search in Go?

The Knuth-Morris-Pratt (KMP) algorithm is an efficient string searching algorithm that searches for occurrences of a word within a main text string. It preprocesses the pattern to create a partial match table (also known as the "prefix" table) that helps in skipping unnecessary comparisons.

package main

import "fmt"

// KMPSearch implements the KMP string search algorithm.
func KMPSearch(pattern, text string) []int {
    m := len(pattern)
    n := len(text)
    lps := computeLPSArray(pattern)
    indices := []int{}

    i, j := 0, 0
    for i < n {
        if pattern[j] == text[i] {
            i++
            j++
        }
        if j == m {
            indices = append(indices, i-j)
            j = lps[j-1]
        } else if i < n && pattern[j] != text[i] {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    return indices
}

// computeLPSArray computes the longest prefix which is also suffix array for KMP.
func computeLPSArray(pattern string) []int {
    length := 0
    lps := make([]int, len(pattern))
    lps[0] = 0
    i := 1

    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

func main() {
    text := "ABABDABACDABABCABAB"
    pattern := "ABABCABAB"
    result := KMPSearch(pattern, text)

    fmt.Println("Pattern found at indices:", result)
}