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