🏷️ 知识点：KMP算法
KMP 算法使用修正后的 next 数组进行模式匹配，模式串 S = “aabaab”，当主串中某字符与 S 中某字符失去配对时，S 将向右滑动的最长距离是（ ）
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 位。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 元素 | a | a | b | a | a | b |
| next | -1 | 0 | 1 | 0 | 1 | 2 |
| next_val | -1 | -1 | 1 | -1 | -1 | 1 |
已知字符串 s 为 “abaabaabacacaabaabcc”，模式串 t 为 “abaabc”。采用 KMP 算法进行匹配，第一次出现“失配”（s[i] ≠ t[j]）时，i = j = 5，则下次开始匹配时，i 和 j 的值分别是（ ）。
A. i = 1, j = 0
B. i = 5, j = 0
C. i = 5, j = 2
D. i = 6, j = 2
[tag_link]
正确答案：C由题中失配 s[i] ≠ s[j] 时，i = j = 5", 可知题中的主串和模式串 的位序都是从 0 开始的（要注意灵活应变）。按照 next 数组生成算法，对于 t 有：
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| t | a | b | a | a | b | b |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
依据 KMP 算法 “当失配时，i 不变，j 回退到 next[j] 的位置并重新比较”，当失配 s[i] ≠ s[j]时，i=j=5, 由上表不难得出 next[j]=next[5]=2（位序从 0 开始）。从而最后结果应为 i=5（i 保持不变），j=2 。
设主串 T=“abaabaabcabaabc”，模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。
A. 9 B. 10 C. 12 D. 15
[tag_link]
正确答案：B
假设位序都是从 0 开始的，按照 next 数组生成算法，对于 S 有
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
根据 KMP 算法，第一趟连续对比 6 次，在模式串的 5 号位和主串的 5 号位匹配失败，模式串的下一个比较位置为 next[5]，即下一次比较从模式串的 2 号位和主串 5 号位开始，然后直到模式串 5 号位和主串 8 号位匹配，第二趟比较 4 次，模式串匹配成功。单个字符的比较次数为 10 次，所以选 B。