数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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。
正文完