单选题

在字符匹配 KMP 算法中， 字符串‘ababaabab’ 的 next 值是（     ）。

【正确答案】 A
【答案解析】

字符匹配 KMP 算法中， next 的计算， 实际上就是计算当前字符以及当前字符前面的字符与开头匹配成功后， 当前字符的最终位置， 如果不成功， 就只能单独找第 1 个， 所以它的值只能为 1。 该串对应的 next如表 1 所示：
表1   KMP 算法的 next

位置 1 2 3 4 5 6 7 8 9
串 a b a b a a b a b
next 0 1 1 2 3 4 2 3 4