前置知识

后缀

后缀 是指从某个位置 开始到整个串末尾结束的一个特殊子串。字符串 的从 开头的后缀表示为 ，也就是 。

真后缀 指除了 本身的 的后缀。

举例来说，字符串 abcabcd 的所有后缀为 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd}，而它的真后缀为 {d, cd, bcd, abcd, cabcd, bcabcd}。

前缀

前缀 是指从串首开始到某个位置 结束的一个特殊子串。字符串 的以 结尾的前缀表示为 ，也就是 。

真前缀 指除了 本身的 的前缀。

举例来说，字符串 abcabcd 的所有前缀为 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabc}。1

KMP 算法

定义

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。

下面先直接给出 KMP 的算法流程:

  • 假设现在文本串 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 值（next 数组的求解会在下文的 3.3.3 节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于 1。

很快，你也会意识到 next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果 next [j] = k，代表 j 之前的字符串中有最大长度为 k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到 next [j] 的位置）。如果 next [j] 等于 0 或-1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符，而不是跳到开头，且具体跳过了 k 个字符。

步骤

  • ① 寻找前缀后缀最长公共元素长度

    • 对于 P = p0 p1 ...pj-1 pj，寻找模式串 P 中长度最大且相等的前缀和后缀。如果存在 p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含 pj 的模式串中有最大长度为 k+1 的相同前缀后缀。举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示： > > 比如对于字符串 aba 来说，它有长度为 1 的相同前缀后缀 a；而对于字符串 abab 来说，它有长度为 2 的相同前缀后缀 ab（相同前缀后缀的长度为 k + 1，k + 1 = 2）。

  • ② 求 next 数组

    • next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第 ① 步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第 ① 步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示： > > 比如对于 aba 来说，第 3 个字符 a 之前的字符串 ab 中有长度为 0 的相同前缀后缀，所以第 3 个字符 a 对应的 next 值为 0；而对于 abab 来说，第 4 个字符 b 之前的字符串 aba 中有长度为 1 的相同前缀后缀 a，所以第 4 个字符 b 对应的 next 值为 1（相同前缀后缀的长度为 k，k = 1）。

  • ③ 根据 next 数组进行匹配

    • 匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀 pj-k pj-k+1, ..., pj-1 跟文本串 si-k si-k+1, ..., si-1 匹配成功，但 pj 跟 si 匹配失败时，因为 next[j] = k，相当于在不包含 pj 的模式串中有最大长度为 k 的相同前缀后缀，即 p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令 j = next[j]，从而让模式串右移 j - next[j] 位，使得模式串的前缀 p0 p1, ..., pk-1 对应着文本串 si-k si-k+1, ..., si-1，而后让 pk 跟 si 继续匹配。如下图所示：

综上，KMP 的 next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在 j 处的字符跟文本串在 i 处的字符匹配失配时，下一步用 next [j] 处的字符继续跟文本串 i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

参考