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

数据结构

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

——老子

1

每日一练

1．在字符串模式匹配的 KMP 算法中，求模式的 next 数组值的定义如下：

请问：

（1）当 j=1 时，为什么要取 next[1]=0？

（2）为什么要取 max{K},K 最大是多少？

（3）其它情况是什么情况，为什么取 next[j]=1?

2．给出 KMP 算法中失败函数 f 的定义，并说明利用 f 进行串模式匹配的规则，该算法的技术特点是什么？

正确答案

PS：||代表注释

1．（1）当模式串中第一个字符与主串中某字符比较不等（失配）时，next[1]=0表示模式串中已没有字符可与主串中当前字符s[i]比较，主串当前指针应后移至下一字符，再和模式串中第一字符进行比较。

（2）当主串第i个字符与模式串中第j个字符失配时，若主串i不回溯，则假定模式串第k个字符与主串第i个字符比较，k值应满足条件1<k<j并且‘p １ …p k-1 ’=‘p j-k+1 …p j-1 ’，即k为模式串向后移动的距离，k值有多个，为了不使向右移动丢失可能的匹配，k要取大，由于max{k}表示移动的最大距离，所以取max{k}，k的最大值为j-1。

（3）在上面两种情况外，发生失配时，主串指针i不回溯，在最坏情况下，模式串从第1个字符开始与主串第i个字符比较，以便不致丢失可能的匹配。

2．这里失败函数f，即是通常讲的模式串的next函数。进行模式匹配时，若主串第i个字符与模式串第j个字符发生失配，主串指针i不回溯，和主串第i个字符进行比较的是模式串的第next[j]个字符。模式串的next函数值，只依赖于模式串，和主串无关，可以预先出。

该算法的技术特点是主串指针i不回溯。在经常发生“部分匹配”和主串很大不能一次调入内存时，优点特别突出。

-end-