关注
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函数值来快速回退到合适的位置,从而提高匹配效率。
查看原帖
1 评论
牛客热帖
正在热议
# 机械人,你投提前批了吗? #
11164次浏览 129人参与
# 互联网公司评价 #
234813次浏览 2978人参与
# 正浩创新校招 #
8861次浏览 119人参与
# 国央企求职进展汇总 #
23517次浏览 102人参与
# 寒假躺平还是提前实习 #
18329次浏览 61人参与
# 比亚迪求职进展汇总 #
376637次浏览 2099人参与
# 广发卡校招来了 #
1246次浏览 6人参与
# 在国企工作的人,躺平了吗? #
223063次浏览 3145人参与
# 你怎么评价今年的春招? #
61788次浏览 1003人参与
# 比亚迪秋招开啦,你打算投递吗? #
6218次浏览 95人参与
# 你觉得实习只能是打杂吗? #
11945次浏览 108人参与
# 职场新人生存指南 #
161806次浏览 4953人参与
# 你的简历改到第几版了 #
600466次浏览 8932人参与
# 国企还是互联网,你怎么选? #
59285次浏览 497人参与
# 如果实习可以转正,你会不会放弃秋招 #
128904次浏览 1838人参与
# 通信硬件薪资爆料 #
409696次浏览 3352人参与
# 你的实习什么时候入职 #
42588次浏览 421人参与
# 写简历别走弯路 #
560080次浏览 6985人参与
# 如何写一份好简历 #
534608次浏览 7828人参与
# 影石Insta360求职进展汇总 #
77761次浏览 764人参与
# 硬件人的简历怎么写 #
191851次浏览 2522人参与
# 实习想申请秋招offer,能不能argue薪资 #
12298次浏览 121人参与