#牛客在线求职答疑中心#设主串 s=“aabcbabcaabcaababc ”,模式 t=“abcaababc ”,求出该模式的next 函数值,并画出根据next 函数对其进行匹配过程的示意图
全部评论
next函数是KMP算法中的核心部分,用于记录模式串中每个位置的最长相等前缀后缀长度。对于模式串t="abcaababc",我们可以这样计算next函数值:
1. t[0]='a',最长相等前缀后缀长度为0,next[0]=0;
2. t[1]='b',最长相等前缀后缀长度为0,next[1]=0;
3. t[2]='c',最长相等前缀后缀长度为0,next[2]=0;
4. t[3]='a',最长相等前缀后缀长度为1,next[3]=1;
5. t[4]='a',最长相等前缀后缀长度为2,next[4]=2;
6. t[5]='b',最长相等前缀后缀长度为0,next[5]=0;
7. t[6]='c',最长相等前缀后缀长度为0,next[6]=0;
8. t[7]='a',最长相等前缀后缀长度为1,next[7]=1。
next函数值数组为:***
匹配过程示意图如下:
1. 主串s="aabcbabcaabcaababc",模式串t="abcaababc";
2. 初始化i=0(主串位置),j=0(模式串位置);
3. 比较s[i]和t[j],如果相等,则i++,j++,继续比较;
4. 如果不相等,则j=next[j],即j回退到next[j]的位置,继续比较;
5. 如果j回退到-1,说明匹配失败,i++,重新开始匹配;
6. 如果j回退到0,说明匹配成功,返回匹配成功的位置i-j。
根据这个示意图,你可以看到,当主串s和模式串t不匹配时,我们可以使用next函数值来快速回退到合适的位置,从而提高匹配效率。
相关推荐
09-29 22:58
云南民族大学 增长产品 点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
09-29 13:39
北京科技大学 golang 点赞 评论 收藏
分享