🏷️ 知识点：修正后的 Next 数组

KMP 算法使用修正后的 next 数组进行模式匹配，模式串 S = “aabaab”，当主串中某字符与 S 中某字符失去配对时，S 将向右滑动的最长距离是（ ）

KMP算法

A. 5 B. 4 C. 3 D. 2

[tag_link]

正确答案：A

本题参考 修正后的 next 数组，传统 KMP 使用 next 数组，不过会存在 j=next[j]的情况，因此采用 next_val[] 来优化，处理好 next[] 和 next_val[] 后，举例即可，比如倒数第二个元素 a 匹配失败，会回到 -1 的位置，从 -1 的位置走到 4 的位置需要右滑的距离为 5 位。