KMP 算法

KMP 相比朴素匹配优化了什么？

• 朴素匹配: 失配后文本串起点右移一格, 模式串指针回到 0, 已匹配信息全部丢弃;
• KMP: 失配时文本串指针不回退, 只回退模式串指针;
• 依据: 利用已经匹配成功的前缀信息, 跳过不可能成立的比较;
• 复杂度: 时间 O(m + n), 空间 O(m);

next 数组 (前缀表) 存的是什么？

• 定义: next[i] 表示模式串 P[0..i] 中, 前缀与后缀相等的最大长度 k;
• 语义: P 的前 k 个字符等于 P[0..i] 末尾的 k 个字符;
• 边界: next[0] 恒为 0, 因为长度为 1 的子串没有真前后缀;

为什么失配后可以跳到 next[j - 1]？

• 已知: 失配发生在 T[i] 与 P[j], 说明 T[i-j .. i-1] == P[0 .. j-1];
• 设 k = next[j - 1], 则 P 的前 k 个字符等于这段已匹配部分末尾的 k 个字符;
• 结论: 文本串从 T[i - k] 起已经匹配, 直接比较 T[i] 与 P[k] 即可, 文本串无需回退;
• 循环: 若仍不相等且 k > 0, 继续按 k = next[k - 1] 回退;

如何构造 next 数组并完成匹配？

• 构造: left 记录当前最长公共前后缀长度, right 从 1 开始扫描, 失配时 left = next[left - 1];
• 匹配: 文本串指针 i 单调前进, 失配时 j = next[j - 1];
• 命中: j === P.length 时返回 i - j + 1;

function strStr(haystack: string, needle: string): number {
  const generateNext = (p: string): number[] => {
    const next = new Array<number>(p.length).fill(0);
    let left = 0;
    for (let right = 1; right < p.length; right++) {
      while (left > 0 && p[left] !== p[right]) left = next[left - 1];
      if (p[left] === p[right]) left++;
      next[right] = left;
    }
    return next;
  };

  const next = generateNext(needle);
  let j = 0;
  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1];
    if (haystack[i] === needle[j]) j++;
    if (j === needle.length) return i - j + 1;
  }
  return -1;
}

如何用 next 数组判断字符串由重复子串组成？

• 前提: 若 s == a × n (n > 1), 则 next[s.length - 1] 等于 a × (n - 1) 的长度;
• 判定: next.at(-1) > 0 且 s.length % (s.length - next.at(-1)) === 0;
• 含义: 最短重复单元的长度为 s.length - next.at(-1), 且能整除总长度;
• 复用上一小节的 generateNext;

function repeatedSubstringPattern(s: string): boolean {
  const next = generateNext(s); // generateNext 见上
  const longest = next.at(-1)!;
  return longest > 0 && s.length % (s.length - longest) === 0;
}