[数据结构与算法]kmp算法之我见

KMP算法是一个著名的字符串匹配算法，效率很高，整体思路其实还是比较好理解，比较难理解的部分在于前缀函数。

• 整体思路：
  字符串1: | A | B | C | D | A | B | C | D | A | B | X |
  字符串2: | A | B | C | D | A | B | Y |

对于字符串1和字符串2，在 C和Y字符上不匹配，只需将字符吕串2移动到下面的位置，再继续进行比较即可，而不用像暴力破解的方法那样一位一位进行比较：
字符串1: | A | B | C | D | A | B | C | D | A | B | X |
字符串2: | _ | _ | __ | _ | A | B | C | D | A | B | Y |

这里，就牵涉到所谓前缀函数的求解，主要就是字符串2，首末存在相同子串时（不是镜像子串，即不是 abxxxba，而是 abyyab这样的情形），在第 i 位上与字符串1上对应的字符开始不一致，应该移动到哪里。

• 前缀函数
  关于前缀函数的代码网上有很多，这里直接上代码，

//  这里求字符串needle的前缀函数，m为needle的长度
for i, j := 1, 0; i < m; i++ {
    for j > 0 && needle[i] != needle[j] {
        j = next[j-1]
    }
    if needle[i] == needle[j] {
        j++
    }
    next[i] = j
}

其中，比较难理解的是这里

    ...
    for j > 0 && needle[i] != needle[j] {
        j = next[j-1]
    }
    ...

直接举个例子，就能明白这里为什么要这么处理了

needle = “ABCABDABCABCe”
m = 13
i = 11 ( C ) // sub_str = “ABCABDABCABC”
j = 5 ( D ) // sub_str = “ABCABD”
始终要牢记，我们需要找到 i 的相同前缀。
这里 needle[i] != needle[j]，不是相同前缀，但前面已经有长度为 j 个字符是相同的（ “ABCAB”，当前坐标是j，即j+1个字符导致不是相同前缀，前面的字符串长充是 j）; 那么要满足 i 的相同前缀，就要在这个 j 长度的子串中找到这个子串的相同缀，且该前缀的后面一个字符是 C （=needle[i]）

另外，next[i]是相同前缀的长度，当进行一 次 j = next[j-1] 后，needle[j] 指向的就是相同前缀子串的后面一个字符。那么在求解next[i]时，就只需要迭代进行 j = next[j-1] 直到needle[j] == needle[i]

• 求解
  结合整体思路和前缀函数，在字符串a 中找到字符串b 的过程就相当于在 b + a 中找到长度为 b长度 的相同前缀，且直接从字符串 a 处开始遍历就可以了。答案网上有很多就不解释了，直接上答案

func strStr(haystack, needle string) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }
    pi := make([]int, m)
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && needle[i] != needle[j] {
            j = pi[j-1]
        }
        if needle[i] == needle[j] {
            j++
        }
        pi[i] = j
    }
    for i, j := 0, 0; i < n; i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = pi[j-1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1
}
来源：[力扣（LeetCode28）](https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/)