T6 KMP 修正后的 next 数组 最大向右滑动距离

• next 数组定义
  • 先计算最长相等前后缀数组 lps:
    • lps[i]: 模式串 P[0..i] 的真前缀中，既是前缀又是后缀的最长长度
  • 然后将lps数组右移一位，并将next[0]设为-1
    • next[i] = lps[i-1] (i > 0), next[0] = -1
• 修正后的 next 数组 nextvar
  • 如果 S[i] == S[next[i]], 则 nextvar[i] = nextvar[next[i]]
• 最大向右滑动距离
  • shift[i] = i - nextvar[i]