KMP matching

kmp.go

package main

import (
	"fmt"
)

func Failure(s string) []int {
	res := make([]int, len(s))
	for i := range s {
		var max int

		// build s[0,i] prefix
		var prefixMap = make(map[string]struct{})
		for j := 0; j <= i; j++ {
			prefix := s[0 : j+1]
			prefixMap[prefix] = struct{}{}
		}

		// buid s[1,i] suffix and compare
		for j := 0; j < i; j++ {
			suffix := s[1+j : i+1]
			if _, ok := prefixMap[suffix]; ok {
				if len(suffix) > max {
					max = len(suffix)
				}
			}

		}

		res[i] = max
	}

	return res
}

// search for t in p
func KMPMatch(t, p string) {
	// build the failure array
	f := Failure(p)
	for i := range p {
		fmt.Printf("%2c ", t[i])
	}
	fmt.Println()
	for i := range p {
		fmt.Printf("%2d ", f[i])
	}
	fmt.Println()

	// start the algorithm
	var i, j int = 0, 0
	for i < len(t) {
		// if match
		if t[i] == p[j] {
			// if all p is matched
			if j == len(p)-1 {
				fmt.Println("match", i-j)
				i = i + 1
				j = 0
			} else {
				// expand
				i = i + 1
				j = j + 1
			}
		} else {
			if j > 0 {
				// slide p in t
				j = f[j-1]
			} else {
				i = i + 1
			}
		}
	}
}

func main() {
	KMPMatch("abcdcbabcaabccdcbabcaabc", "abcaabc")
	// a  b  c  d  c  b  a 
	// 0  0  0  1  1  2  3 
	// match 6
	// match 17
}