🏷️ 知识点：KMP 算法
2015 年第 8 题
数据结构
选择题
已知字符串 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 。
2019 年第 9 题
数据结构
选择题
设主串 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。