KMP 的分界线法与 next 数组

KMP 解决的问题与朴素模式匹配相同：在主串中查找模式串第一次出现的位置。区别在于：KMP 发生失配时，主串指针 i 不回退，只根据模式串自身结构调整模式串指针 j。

核心思想

当 S[i] != T[j] 时，T[1..j-1] 已经与主串中的一段字符完全相同。KMP 利用这段“已知匹配信息”，判断模式串应该滑到哪里继续比较。

更直观的手算方式：

  1. 在失配位置前画一条分界线。
  2. 只看分界线之前已经匹配的部分。
  3. 让模式串一步一步后退，直到分界线之前模式串部分能与相应位置的主串部分还能对上，或分界线前的模式串部分为$\emptyset$
  4. 此时 j 指向的位置，就是 next[j]。

这种做法和“最大相等前后缀”本质等价，但计算时更贴近匹配过程：每个 next[j] 都对应“T[j] 失配后该拿谁继续和当前 S[i] 比”。

next 的含义

采用教材常见的 1-based 串下标：

1
2
3
4
5
6
if (S.ch[i] == T.ch[j]) {
    ++i;  // 当前字符匹配，主串继续看下一个字符
    ++j;  // 模式串也继续看下一个字符
} else {
    j = next[j];  // 失配时只回退 j，i 仍停在当前主串字符
}

next[j] 表示：当 T[j] 与 S[i] 失配，且 T[1..j-1] 已经匹配时，模式串指针 j 应退到的位置。

常见约定：

  • next[1] = 0：第一个字符失配，说明当前主串字符无法匹配模式串开头；下一步应移动主串指针。
  • next[2] = 1：第二个字符失配时，尝试让模式串第一个字符与当前主串字符比较。
  • 其他 next[j] 用分界线法计算。

KMP 匹配代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int KMP_Index(SString s, SString t, int next[]) {
    int i = 1;  // 主串 s 的当前比较位置，采用 1-based 下标
    int j = 1;  // 模式串 t 的当前比较位置

    while (i <= s.length && j <= t.length) {
        if (j == 0 || s.ch[i] == t.ch[j]) {
            // j == 0 表示 t[1] 也无法匹配当前 s[i]，
            // 需要放弃当前主串字符，让 i 前进，并把 j 恢复到 1。
            // 字符相等时，说明当前一对字符匹配成功，也同时前进。
            ++i;
            ++j;
        } else {
            // t[j] 失配，但 t[1..j-1] 已匹配。
            // next[j] 给出模式串可保留的前缀之后，下一次应比较的位置。
            // 这里主串指针 i 不回退，避免重复比较已经确认匹配的字符。
            j = next[j];
        }
    }

    if (j > t.length) {
        // 匹配成功时，i 已经指向匹配段后一个位置。
        // 因此起始位置 = i - 模式串长度。
        return i - t.length;
    }

    // 主串扫描完仍未让 j 越过模式串末尾，表示匹配失败。
    return 0;
}

j == 0 的含义：模式串第一个字符也无法匹配当前主串字符，需要让主串指针前进，并让 j 回到 1。

手算 next 的要点

Example
对模式串 `T = abaabc`，教材常见结果为：
j 1 2 3 4 5 6
T[j] a b a a b c
next[j] 0 1 1 2 2 3

理解方式：

  • next[1] = 0 固定。
  • next[2] = 1 固定。
  • next[6] = 3：若 c 失配，分界线前是 abaab，后退后可保留前后能对上的 ab，下一次用 T[3] 继续比较。

复杂度

KMP 总复杂度为 $O(n + m)$：

  • 求 next 数组需要 $O(m)$。
  • 匹配过程主串指针不回退，最多线性扫描主串，复杂度 $O(n)$。

优化

详见kmp-nextval