第 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 。