KMP思路分析
1、为什么需要使用KMP
- 最先想到的方法 - 暴力，使用两层for循环，时间复杂度O(m*n)
- 显然时间复杂度可以太高，而且可以进行优化
- 如何优化？ — KMP 利用前缀 和 后缀找到最大相等长度
- 我的理解： 利用对称进行偏移，如此就不必每次都要便利模板串了
2、KMP 为什么要 使用后缀数组 – 分析
分析:
这里不想等，实际上因为前面相同，所有无论是模板串还是匹配串，相同的前后缀都会相同，所有可以偏移 ,偏移之后前面的部分还是想等，如下
这个储存偏移的数组，就是next数组
3、如何求next数组？
4、第一种情况，如 ABBA ， 有相同的前后最A，如果第五个字母是B ，那么第二个字符对应最后一个字符就是AB，ne[5] = 2 ,直接加1
5、第二种情况，如上图
假设a和b部分是相等的，比较 a + m 和 b + k，如果不相等，如下：
- 可以假设a中相同的前后缀是a1、a2，那么对应的b中有对应的前后缀是b1、b2,此时 a1 == b2
- 接下来比较a1 + x 和 b2 + k
- 依次类推
6、那么如何利用一个找不到就找更小的前后缀呢，利用next数组，因为在k之前的数组都是更新好的数组，因此让前缀的尾的指针不断移动进行判断，即
j = ne[j-1]
7、整体代码如下
func strStr(haystack string, needle string) int { n, m := len(haystack), len(needle) if m == 0 { return 0 } ne := make([]int, m) GetNext(ne, needle) //进行判断了 for i, j := 0, 0; i < n; i++ { //利用后缀数组进行比较 for j > 0 && haystack[i] != needle[j] { j = ne[j-1] } //相等就比较下一个 if haystack[i] == needle[j] { j++ } if j == m { return i - j + 1 } } return -1 } func GetNext(ne []int, st string) { j := 0 //是前缀最后一个字母 for i := 1; i < len(st); i++ { //如果不相等 for j > 0 && st[j] != st[i] { j = ne[j-1] } //如果相等 if st[i] == st[j] { j++ } ne[i] = j } fmt.Println(ne) }
