🧠 KMP 算法 —— next 数组求法

⭐ 下标从 0 开始

  • next[0] = -1
  • 当 i ≥ 1：设 k 为 T[0...i-1] 的最长相等前后缀长度
    • k = 0 → next[i] = 0
    • k > 0 → next[i] = k

⭐ 下标从 1 开始

  • next[1] = 0
  • 当 i ≥ 2：设 k 为 T[1...i-1] 的最长相等前后缀长度
    • k = 0 → next[i] = 1
    • k > 0 → next[i] = k + 1

🔑 滑动距离

模式串向右滑动 = j - next[j]（或 j - nextval[j]）

⚠️ 与下标从 0 还是从 1 开始无关

💡 大白话版

下标从 1 开始：

next[1] = 0，next[2] = 1，直接背

从第 3 个位置开始 → 看 T[1...i-1] 这段，从头数和从尾数，能对上的最长那段：

  • 对上了，长度 k → next[i] = k + 1
  • 对不上 → next[i] = 1

下标从 0 开始：

next[0] = -1，直接背

从第 1 个位置开始 → 看 T[0...i-1]，一样找最长相等前后缀：

  • 找到了，长度 k → next[i] = k
  • 找不到 → next[i] = 0

举个例子 🌰 模式串 "ababaa"

i（从1开始） 看 T[1…i-1] 最长相等前后缀 next[i]
1 — — 0
2 "a" 无 1
3 "ab" 无 1
4 "aba" "a" (k=1) 2
5 "abab" "ab" (k=2) 3
6 "ababa" "aba" (k=3) 4

🎬 视频讲解