go KMP

kmp 想必很多人已经知道了，先求next数组，再去匹配

code

package main
import "fmt"
func main () {

    p := "abcabe"
    s := "abcabfabcabef"

    next := make([]int, len(p))
    next[0] = -1

    // fmt.Println(next)

    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
    }

    fmt.Println("p的next数组：")
    fmt.Println(next)

    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 {
            fmt.Printf("find %s in %s, index is %d", p, s, i-j)
            j = next[j]
        }
    }
}

结果

p的next数组：

[-1 -1 -1 0 1 -1]

find abcabe in abcabfabcabef, index is 6