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

数据结构

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

——老子

1

每日一练

1．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为 m，模式的长度为 n，则在主串中寻找模式的 KMP 算法的时间复杂性是多少？如果，某一模式 P=’abcaacabaca’，请给出它的NEXT 函数值及 NEXT 函数的修正值 NEXTVAL 之值。

2．设目标为 S=‘abcaabbcaaabababaabca’，模式为 P=‘babab’，

（1）手工计算模式 P 的 nextval 数组的值；

（2）写出利用求得的 nextval 数组，按 KMP 算法对目标 S 进行模式匹配的过程。

3．用无回溯的模式匹配法（KMP 法）及快速的无回溯的模式匹配法求模式串 T 的 next[j]值，添入下面表中：

正确答案

PS：||代表注释

1．KMP算法的时间复杂性是O（m+n）。

p的next和nextval值分别为01112212321和01102201320。

2．（1）p的nextval函数值为01010。（next函数值为01123）

（2）利用所得nextval数值，手工模拟对s的匹配过程，与上题类似。

3．模式串T的next和nextval值分别为0121123和0021002。

-end-