关注
知模式串为“aaabab”,主串为“aaabbaabaaababb”,使用KMP算法(Knuth-Morris-Pratt)进行模式匹配时,我们首先需要构建一个部分匹配表(也称为“失败函数”或“next数组”),用于在不匹配时确定模式串的下一个匹配位置。
以下是构建部分匹配表的步骤:
1. 初始化部分匹配表,对于模式串“aaabab”,部分匹配表如下:
- a: 0
- aa: 0
- aaab: 0
- aaaba: 1
- aaabab: 2
2. 接下来,我们使用这个表来进行模式匹配。我们从主串的起始位置开始,尝试将模式串与主串进行匹配。
3. 当我们发现不匹配时,我们查看部分匹配表来确定模式串的下一个匹配位置,而不是从模式串的开始重新匹配。
以下是匹配过程:
- 从主串的第1个字符开始,我们发现“a”与模式串的第一个字符匹配,继续比较。
- 接下来,“aa”与模式串的前两个字符匹配,继续比较。
- 然后,“aaab”与模式串的前三个字符匹配,继续比较。
- 接着,“aaaba”与模式串的前四个字符匹配,但第五个字符不匹配。根据部分匹配表,我们知道下一个匹配位置应该是从模式串的第二个字符开始,即“aab”。
- 继续匹配,我们发现“aab”与主串的第五、六、七个字符匹配,但第八个字符不匹配。根据部分匹配表,下一个匹配位置是“ab”。
- 继续匹配,我们发现“ab”与主串的第九、十个字符匹配,但第十一个字符不匹配。根据部分匹配表,下一个匹配位置是“b”。
- 继续匹配,我们发现“b”与主串的第十二个字符匹配,但第十三个字符不匹配。由于模式串已经完全匹配过一次,我们可以直接跳过前面的匹配,从模式串的第二个字符“a”开始匹配。
- 继续匹配,我们发现“a”与主串的第十四个字符匹配,继续比较。
- 接下来,“aa”与模式串的前两个字符匹配,继续比较。
- 然后,“aaab”与模式串的前三个字符匹配,继续比较。
- 接着,“aaaba”与模式串的前四个字符匹配,但第五个字符不匹配。根据部分匹配表,下一个匹配位置是“aab”。
- 最后,我们发现模式串“aaabab”在主串“aaabbaabaaababb”中的位置是从第七个字符开始的。
使用KMP算法,我们可以高效地找到模式串在主串中的位置,避免了不必要的重复比较。
查看原帖
点赞 评论
相关推荐
10-18 04:17
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
250569次浏览 2035人参与
# 学历or实习经历,哪个更重要 #
41251次浏览 300人参与
# 北方华创开奖 #
22982次浏览 259人参与
# 地方国企笔面经互助 #
2607次浏览 6人参与
# 应届生被毁约被毁意向了怎么办 #
27297次浏览 238人参与
# 选完offer后,你后悔学本专业吗 #
11119次浏览 77人参与
# 你最想要的公司福利是? #
40321次浏览 127人参与
# 查收我的offer竞争力报告 #
17211次浏览 229人参与
# 机械应届生薪资要多少才合适? #
12418次浏览 60人参与
# 一觉醒来,我觉醒了超级打工人系统 #
2962次浏览 35人参与
# 如何写一份好简历 #
602737次浏览 8451人参与
# 秋招OC许愿 #
226869次浏览 1873人参与
# 秋招被确诊为…… #
56513次浏览 310人参与
# 你觉得第一学历对求职有影响吗? #
14910次浏览 121人参与
# 总结:哪家公司面试体验感最差 #
25815次浏览 129人参与
# 面试题刺客退退退 #
137360次浏览 2092人参与
# 不给转正的实习,你还去吗 #
1517440次浏览 16976人参与
# 来聊聊机械薪资天花板是哪家 #
64640次浏览 436人参与
# 大疆求职进展汇总 #
404984次浏览 2890人参与
# 校招入职后的感受 #
157035次浏览 1961人参与
# 实习,投递多份简历没人回复怎么办 #
2391527次浏览 34297人参与