数据结构 | 每日一练（108）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．已知模式串 t=‘abcaabbabcab’写出用 KMP 法求得的每个字符对应的 next 和 nextval 函数值。

2．试利用 KMP 算法和改进算法分别求 p1=‘abaabaa’和 p2=‘aabbaab’的 next 函数和 nextval 函数。

3．已知 KMP 串匹配算法中子串为 babababaa,写出 next 数组改进后的 next 数组信息值（要求写出数组下标起点）。

4．求模式串 T=‘abcaabbac' 的失败函数 Next(j)值。

5．字符串的模式匹配 KMP 算法中,失败函数(NEXT)是如何定义的?计算模式串 p=‘aabaabaaabc’中各字符的失败函数值.

正确答案

PS：||代表注释

1．

2．p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：0121123和0021002。

3．next数组值为011234567 改进后的next数组信息值为010101017。

4．011122312。

5．next定义见题上面1。串p的next函数值为：01212345634。