题11
题目
【2019 统考真题】设主串 T = 'abaabaabcabaabc' ,模式串 S = 'abaabc' ,采用 KMP 算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是 ( ).
A. 9
B. 10
C. 12
D. 15
分析
假设位序从 0 开始的, 按照 next 数组生成算法, 对于 S 有
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | C |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
第一趟连续比较 6 次, 在模式串的 5 号位和主串的 5 号位匹配失败, 模式串的下一个比较位置为 next[5], 即下一次比较从模式串的 2 号位和主串的 5 号位开始, 然后直到模式串的 5 号位和主串的 8 号位匹配, 第二趟比较 4 次, 匹配成功。 | ||||||
| 单个字符的比较次数为 10 次。 |
解
B