Skip to content

Instantly share code, notes, and snippets.

@ae6up ae6up/KMP
Last active Dec 16, 2015

Embed
What would you like to do?
Working though the Knuth-Morris-Pratt algorithm.
package main
import "fmt"
//naive approach
func inStr(s, w string) int {
pos, i := 0, 0
for pos+i < len(s) {
//fmt.Printf("%x: s[%x+%x] == w[%x] / %c == %c\n", pos, pos, i, i, s[pos+i], w[i])
if s[pos+i] == w[i] {
if i == len(w)-1 {
return pos
}
i++
} else {
pos++
i = 0
}
}
return -1
}
func kmp(s, w string) int {
t := preprocess(w)
pos, i := 0, 0
for pos+i < len(s) {
//fmt.Printf("%x: s[%x+%x] == w[%x] / %c == %c\n", pos, pos, i, i, s[pos+i], w[i])
if s[pos+i] == w[i] {
if i == len(w)-1 {
return pos
}
i++
} else {
pos = pos + i - t[i]
if t[i] > 0 {
i = t[i]
} else {
i = 0
}
}
}
return -1
}
func preprocess(w string) []int {
t := make([]int, len(w))
if len(w) > 0 {
t[0] = -1
}
pos, cnd := 2, 0
for pos < len(w) {
//fmt.Printf("%x: w[%x-1] == w[%x] / %c == %c\n", pos, pos, cnd, w[pos-1], w[cnd])
if w[pos-1] == w[cnd] {
cnd++
t[pos] = cnd
pos++
} else if cnd > 0 {
cnd = t[cnd]
} else {
t[pos] = 0
pos++
}
}
return t
}
func main() {
//fmt.Println(preprocess(""))
//fmt.Println(preprocess("abcdefghij"))
//fmt.Println(preprocess("a"))
//fmt.Println(preprocess("aaaf"))
//fmt.Println(preprocess("ababccabaabcdef"))
//fmt.Println(preprocess("abcdefabcdef"))
//fmt.Println(preprocess("aaaaaaa"))
//fmt.Println(inStr("aaaaaaaf", "aaaf"))
//fmt.Println(kmp("aaaaaaaf", "aaaf"))
//fmt.Println(kmp("abcdef", "efg"))
//fmt.Println(kmp("abcdef", "cd"))
fmt.Println(kmp("ABC ABCDAB ABCDABCDABDE", "ABCDABD"))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.