KMP：分界线法求 next
例：模式串 T = abaabc，演示 T[6] 失配时 j 如何一步步后退。

1. T[6] 失配：只看分界线之前

下标 j
1
2
3
4
5
6
T
a
b
a
a
b
c

若比较到 T[6] 时失配，说明 T[1..5] = abaab 已经匹配。

分界线画在失配位置前。后退时只利用分界线前的已匹配段 abaab。
已知：T[1..5] 已匹配
目标：找到 T[6] 失配后，j 应回退到哪个位置继续比较

2. 第一次尝试：保留 4 个字符

前缀长度 4取 T[1..4]

前缀
a
b
a
a

后缀长度 4取 T[2..5]

后缀
b
a
a
b
abaa != baab，不能保留 4 个已匹配字符，继续后退。
若 next[6] = 5，则表示下一次用 T[5] 比较；
这要求已匹配段中长度为 4 的前缀和后缀相同，但这里不成立。

3. 第二次尝试：保留 3 个字符

前缀长度 3取 T[1..3]

前缀
a
b
a

后缀长度 3取 T[3..5]

后缀
a
a
b
aba != aab，不能保留 3 个已匹配字符，继续后退。
若 next[6] = 4，则下一次用 T[4] 比较；
这要求长度为 3 的前缀和后缀相同，但这里不成立。

4. 第三次尝试：保留 2 个字符，成功

前缀长度 2取 T[1..2]

前缀
a
b

后缀长度 2取 T[4..5]

后缀
a
b
ab == ab，可以保留 2 个已匹配字符。所以下一次从 T[3] 继续比较。
保留字符数 = 2
下一次比较位置 = 保留字符数 + 1 = 3
所以 next[6] = 3

5. 对齐后的状态：j 退到 3，i 不动

主串片段
a
b
a
a
b
?
T 原位置
a
b
a
a
b
c
T 后退后
a
b
a
a

后退后，模式串开头的 ab 与主串中已匹配段末尾的 ab 对齐。当前主串字符仍是刚才让 T[6] 失配的字符。

因此下一次比较不是从头开始，而是让 T[3] 和当前 S[i] 比较。

6. next[6] 的含义

next[6] = 3 表示：当 T[6] 失配，并且 T[1..5] 已匹配时，模式串指针 j 回退到 3。

if (S.ch[i] == T.ch[j]) {
    ++i;  // 当前字符匹配，主串继续看下一个字符
    ++j;  // 模式串也继续看下一个字符
} else {
    // T[6] 失配时，T[1..5] 已经匹配。
    // next[6] = 3 表示保留前后能对齐的 "ab"，
    // 下一次用 T[3] 和当前 S[i] 比较，主串指针 i 不动。
    j = next[j];
}
主串指针 i 不回退；被保留下来的 ab 不需要重新比较。

7. T = abaabc 的 next 数组

j
1
2
3
4
5
6
T[j]
a
b
a
a
b
c
next[j]
0
1
1
2
2
3

手算时不要直接背表。对每个 j，都把分界线画在 T[j] 前面，只看 T[1..j-1]，再从最长可保留部分开始逐步后退。

点击按钮或使用方向键翻页。