数据结构考研分类复习真题 第四章 答案[10]

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

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

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

．这里失败函数f即是通常讲的模式串的next函数其定义见本章应用题的第题

进行模式匹配时若主串第i个字符与模式串第j个字符发生失配主串指针i不回溯和主串第i个字符进行比较的是模式串的第next[j]个字符模式串的next函数值只依赖于模式串和主串无关可以预先求出

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

．失败函数（即next）的值只取决于模式串自身若第j个字符与主串第i个字符失配时假定主串不回溯模式串用第k（即next[j]）个字符与第i个相比有 p…pk=pjk+…pj为了不因模式串右移与主串第i个字符比较而丢失可能的匹配对于上式中存在的多个k值应取其中最大的一个这样因jk最小即模式串向右滑动的位数最小避免因右移造成的可能匹配的丢失

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []