other_problems/kmp.go

package main

import "fmt"

func main() {
	pattern := []byte("A")
	text := []byte("ABABABABCAIABABCSS")
	// 1. &#29983;&#25104;pattern&#30340;&#21069;&#32512;&#34920;
	prefix := prefixTable(pattern)
	fmt.Println(prefix)
	// 2. &#21305;&#37197;
	kmpSearch(pattern, text)
}

func kmpSearch(pattern, text []byte) {
	prefix := prefixTable(pattern)
	m, n := len(pattern), len(text)
	i, j := 0, 0
	for j < n {
		// &#25214;&#21040;match: i&#24050;&#32463;&#36941;&#21382;&#21040;&#26368;&#21518;&#19968;&#20301;&#24182;&#19988;&#30456;&#31561;
		if i == m-1 && pattern[i] == text[j] {
			fmt.Println("Found a match at: ", j-i)
			i = prefix[i]
			if m == 1 {
				i++
				j++
				continue
			}
		}
		if pattern[i] == text[j] {
			i++
			j++
		} else {
			i = prefix[i]
			if i == -1 {
				i++
				j++
			}
		}
	}
}

func prefixTable(pattern []byte) []int {
	n := len(pattern)
	prefix := make([]int, n)
	prefix[0] = 0
	l := 0
	i := 1
	for i < n {
		if pattern[i] == pattern[l] {
			l++
			prefix[i] = l
			i++
		} else {
			if l == 0 {
				prefix[i] = 0
				i++
			} else {
				l = prefix[l-1]
			}
		}
	}
	// &#23558;&#21069;&#32512;&#34920;&#24448;&#21518;&#31227;&#19968;&#20301;&#65292;&#26041;&#20415;&#25628;&#32034;&#26102;&#30340;&#31227;&#20301;&#25805;&#20316;
	for i := n - 1; i > 0; i-- {
		prefix[i] = prefix[i-1]
	}
	prefix[0] = -1
	return prefix
}