解决在主串中快速匹配子串的问题
传统暴力算法每次失败都要从头开始，时间复杂度是$$ O(m * n) $$,效率比较差

核心思想：利用已经匹配过的信息，避免主串指针回退，从而加速匹配
KMP是如何实现优化的呢？

  • 前缀表
    next[i] = 当 needle[0..i]不匹配时，应跳回的下一个可匹配位置（前缀长度）

假设我们匹配：

1
2
3
4
5
6
7
8
9
10
11
12
13
主串：  ABC ABCDAB ABCDABCDABDE
子串：     ABCDABD

当匹配到：

ABCDAB **E**
ABCDAB **D**

在 E != D 时：

暴力算法会回到开头：
   ABCDAB E
-> A

但 KMP 会使用 next 数组得知：

已匹配的 “ABCDAB” 中前缀和后缀的最长相等部分是 “AB”（长度 2）

所以只需跳回到 needle[2] 继续匹配，而无须重来。

这大幅减少了重复比较。

为什么next数组可以帮助跳位置
因为next[i]表示的是以 i 为结尾的子串中，最长相等前后缀的长度
当子串和主串遇到不相等的字符时，子串会回到前缀的后一个位置与主串继续比较

一个例题

  • 构造next数组,找出模式串内每个位置 i 的最长前后缀
1
2
3
4
5
6
7
8
9
10
for i := 1; i < len(s); i++ {
    for j > 0 && s[i] != s[j] {
        j = next[j-1]
    }
    if s[i] == s[j] {
        j++
    }
    next[i] = j
}

  • 利用next进行匹配,当遇到不匹配：使用 next 数组跳转，而不是暴力回退
1
2
3
4
5
6
7
8
9
10
11
12
for i := 0; i < len(haystack); i++ {
    for j > 0 && haystack[i] != needle[j] {
        j = next[j-1]
    }
    if haystack[i] == needle[j] {
        j++
    }
    if j == n {
        return i - n + 1
    }
}