90 lines
1.9 KiB
Go
90 lines
1.9 KiB
Go
package src
|
||
|
||
// 暴力匹配
|
||
func bf(s, p string) int {
|
||
n := len(s)
|
||
m := len(p)
|
||
if n < m {
|
||
return -1
|
||
}
|
||
|
||
for i := 0; i <= n-m; i++ {
|
||
j := 0
|
||
for j < m {
|
||
// 如果主串与模式串不匹配，则主串向右移动一个字符,模式串从头开始匹配
|
||
if s[i+j] != p[j] {
|
||
break
|
||
}
|
||
j++
|
||
}
|
||
if j == m {
|
||
return i
|
||
}
|
||
}
|
||
|
||
return -1
|
||
}
|
||
|
||
func kmp(s, p string) int {
|
||
n := len(s)
|
||
m := len(p)
|
||
if n < m {
|
||
return -1
|
||
}
|
||
next := getNext(p)
|
||
|
||
for i := 0; i <= n-m; i++ {
|
||
j := 0
|
||
for j < m {
|
||
// 暴力匹配算法当模式串和主串不匹配时，主串匹配下标 +1，模式串匹配下标置为 0，
|
||
// KMP 算法优化点在于将模式串下标置为不匹配字符前一个字符对应 next 数组的值
|
||
if s[i+j] != p[j] {
|
||
// 当模式串与主串不匹配时，如果不匹配字符对应模式串下标大于 j > 0 (非首个模式串字符)，
|
||
// 并且此字符前一个字符对应字符串部分匹配表中的值 next[j - 1] 也大于 0，
|
||
// j - next[j - 1] 即模式串为后移的位数，等价于 j 置为 next[j - 1]
|
||
|
||
if j != 0 && next[j-1] != 0 {
|
||
// j 后移 j-next[j-1]，等价于 j = next[j-1]
|
||
j = next[j-1]
|
||
} else {
|
||
break
|
||
}
|
||
}
|
||
j++
|
||
}
|
||
if j == m {
|
||
return i
|
||
}
|
||
}
|
||
|
||
return -1
|
||
}
|
||
|
||
func getNext(p string) []int {
|
||
n := len(p)
|
||
next := make([]int, n)
|
||
next[0] = 0
|
||
k := 0
|
||
|
||
// 根据已知 next 数组的前 i-1 位推测第 i 位
|
||
for i := 1; i < n; i++ {
|
||
for k > 0 && p[k] != p[i] {
|
||
// k 为 p[0, i) 子串最大匹配前后缀长度
|
||
// p[0, k) 为 p[0, i) 子串最大匹配前缀子串
|
||
|
||
// 若：1、p[k] != p[i]，则求 p[0, i] 子串最大匹配前后缀长度问题
|
||
// 转换成了求 p[0, k) 子串最大匹配前后缀长度问题
|
||
// 循环直到 p[k] == p[i] (下一步处理) 或 k == 0
|
||
k = next[k]
|
||
}
|
||
|
||
// 若：2、p[k] == p[i]，则 p[0, i] 子串最大匹配前后缀长度为 k + 1
|
||
if p[k] == p[i] {
|
||
k++
|
||
}
|
||
|
||
next[i] = k
|
||
}
|
||
return next
|
||
}
|