KMP.go

package main

import (
	"fmt"
)

func prefixTable(p string) []int {
	f := make([]int, len(p))
	i, j := 1, 0
	for i < len(p) {
		if p[i] == p[j] {
			f[i] = j + 1
			i++
			j++
		} else if j > 0 {
			j = f[j-1]
		} else {
			f[i] = 0
			i++
		}
	}
	return f
}

func KMP(s, p string) int {
	i, j := 0, 0
	f := prefixTable(p)
	for i < len(s) {
		if s[i] == p[j] {
			if j == len(p)-1 {
				return i - j
			} else {
				i++
				j++
			}
		} else if j > 0 {
			j = f[j-1]
		} else {
			i++
		}
	}
	return -1
}

func main() {
	f := prefixTable("ababaca")
	p := KMP("bacbabababacaca", "ababaca")
	fmt.Println(f, p)
}