KMP
1.求prefix数组
func prefix_table(pattern string, prefix []int, n int) {
i := 1
prefix[0] = 0
len := 0
for i < n {
if pattern[i] == pattern[len] {
len++
prefix[i] = len
i++
} else {
if len == 0 {
prefix[i] = 0
i++
} else {
len = prefix[len-1]
}
}
}
//move -> 1
for i = n - 1; i > 0; i-- {
prefix[i] = prefix[i-1]
}
prefix[0] = -1
}
2.KMP搜索
func kmp_search(str string, pattern string) int {
n, m := len(pattern), len(str)
prefix := make([]int, n)
prefix_table(pattern, prefix, n)
// kmp
// str i m
// pattern j n
i, j := 0, 0
for i < m {
if str[i] == pattern[j] {
if j == n-1 {
return i - n + 1
// j = prefix[j]
}
i++
j++
} else {
j = prefix[j]
if j == -1 {
i++
j++
}
}
}
return -1
}