考研笔记

板子：KMP 的 next 与 nextval（教材口径）

★ 级：以手算为主，代码按教材写。下标从 1 开始，next[1] = 0。手算方法和算竞口径的换算见 速查：KMP 的 next 与 nextval。

代码

void getNext(char T[], int m, int next[]) {  // 模式串 T[1..m]，T[0] 不用
    int i = 1, j = 0;                        // j == 0 表示一个字符都没对上
    next[1] = 0;
    while (i < m) {                          // i 每后移一次就求出一个 next[i]，最后一个是 next[m]
        if (j == 0 || T[i] == T[j]) {        // 对上了，或者已经退到头：相等前后缀长度 +1
            i++; j++;
            next[i] = j;
        } else j = next[j];                  // 没对上：j 按 next 往回退，再比较
    }
}
 
void getNextval(char T[], int m, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < m) {
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            if (T[i] != T[j]) nextval[i] = j;        // 跳过去的字符和自己不同：与 next 相同
            else nextval[i] = nextval[j];            // 相同：跳过去也一定失配，继续往前跳
        } else j = nextval[j];
    }
}
 
int indexKMP(char S[], int n, char T[], int m, int next[]) {   // 主串 S[1..n]；返回匹配起点，没有返回 0
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (j == 0 || S[i] == T[j]) { i++; j++; }  // 对上了（或 j 退到 0）：两个指针都后移
        else j = next[j];                          // 失配：i 不动，j 退到 next[j]
    }
    if (j > m) return i - m;                       // 模式串全部对上了
    return 0;
}

复杂度：求 next 为 ，匹配为 ，合计 。

例：abcac 的 next 是 0 1 1 1 2；aaaab 的 nextval 是 0 0 0 0 4。

关键边界

位置为什么
while (i < m)，不是 <=循环里先 i++ 再给 next[i] 赋值，i 最后停在 ，正好求到 next[m]
j == 0 这个条件j 退到 0 表示没有相等的前后缀，接下来两个指针一起后移，得到 next[i] = 1
匹配时失配只动 j主串指针 i 不回溯，这是 KMP 的主要优点
返回 i - m循环结束时 i 指向匹配段后面一个位置

易错点

  • **算竞口径下标从 0 开始，写成 fail[0] = -1，和这里每一项都差 1。**手算题一律按教材口径。
  • 用 nextval 匹配时，匹配函数不用改，把 nextval 当成 next 传进去就行。
  • 求 nextval 比较的是 T[i] 和 T[j]，也就是「当前字符」和「失配后要跳去比较的那个字符」。

链接

反向链接