KMP 算法
最后更新于：2022-04-02 04:22:48
[TOC]
## 场景
在一个字符串中是否包含另一个字符串
## 概述
- 一句话概括,KMP算法的核心是已经匹配的字符不会重复匹配
- KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组
### 图示
## 解析
假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
* 如果 j = -1，或者当前字符匹配成功（即 S\[i\] == P\[j\]），都令 i++，j++，继续匹配下一个字符；
* 如果 j != -1，且当前字符匹配失败（即 S\[i\] != P\[j\]），则令 i 不变，j = next\[j\]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next \[j\] 位。
* 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值，即**移动的实际位数为：j - next\[j\]**
* 如果 next [j] 等于 0 或 -1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符
思路
1.构造next数组（初始化->处理前后缀不相同的情况->处理前后缀相同的情况）
2.使用next数组来做匹配
golang 实现
```
func strStr(haystack string, needle string) int {
n:=len(haystack)
m:=len(needle)
if (m==0){
return 0
}
if (n0 && haystack[i]!=needle[q]{
q=next[q-1]
}
if ( haystack[i]==needle[q]){
q++
}
if (q==m){
return i+1-m;
}
}
return -1
}
func compute_next( pattern string) []int {
n:=len(pattern)
next:=make([]int,n)
k:=0
for q:=1;q0 && ( pattern[k]!=pattern[q]){
k=next[k-1];
}
if ( pattern[k]==pattern[q]){
k++;
}
next[q]=k;
}
return next
}
```
';