KMP
算法思路
有如下情况（这里原串&子串都是从1开始）
原串\(s\)（以下简称\(s\)）和子串\(p\)（以下简称\(p\)）进行匹配，直到黑色分界线时都是匹配的，直到其后面一个元素不相等，\(s[i] \ne p[j + 1]\)
首先在这样的情况下，我们可以通过移动\(p\)来实现\(s[i] = p[j + 1]\)；如果直接回溯\(s\)的话，效率过低。
图如下：
那么这样就可以运用到之前已经匹配了的\(s\)，这里不难看出，这个\(p\)移动的距离就是\(next[j]\)；而通过观察发现这个\(next[j]\)就是寻找到一个与以j为后缀的串相等的最长的前缀串（不包含其自身）；所以那么\(s\)与\(p\)匹配的过程中若不匹配了，那么\(p\)就回退到\(next[j]\)，然后再进行比较，直到退无可退或者是已经匹配了。当\(j = len(p)\)时，就表示匹配成功，同时将\(j = next[j]\)（因为匹配成功后，之后的情况就是不匹配了，与之前的情况类似，所以也需要回退一下）
match code
// 返回匹配成功后，开始进行匹配的位置
// 因为在匹配演示的过程中是j + 1 和 i进行比较的，故s从1开始，p从0开始
func match(s, p []byte) (res []int) {
n := len(s)
for i, j := 1, 0; i <= n; i++ {
for j != 0 && s[i] != p[j + 1] {
j = next[j]
}
if s[i] == p[j + 1] {
j++
}
if j == n {
res = append(res, j - n + 1)
j = next[j]
}
}
return
}
当然还需要预处理出\(next\)数组，仔细分析以下，其实match的过程是类似的。当\(p[i] != p[j + 1]\)，那么也就开始移动\(p\)串，直到其为相等或者是到了退无可退的情况；
pre-treatment code
// 从2开始是因为next[1]是退无可退的情况，故next[1] = 1；所以从2开始即可
func preTreatment(p []byte) (next []int) {
m := len(p)
for i, j := 2, 0; i <= m; i++ {
for j != 0 && p[i] != p[j + 1] {
j = next[j]
}
if p[i] == p[j + 1] {
j++
}
next[j] = j
}
return
}