关注
知模式串为“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算法,我们可以高效地找到模式串在主串中的位置,避免了不必要的重复比较。
查看原帖
点赞 评论
相关推荐
牛客热帖
正在热议
# 25届秋招公司红黑榜 #
83530次浏览 504人参与
# 双非能在秋招上岸吗? #
26657次浏览 173人参与
# 简历被挂麻了,求建议 #
2318158次浏览 31965人参与
# 秋招拿一个offer可以躺平吗 #
83028次浏览 675人参与
# 你的秋招进展怎么样了 #
1580468次浏览 24157人参与
# 求职你最看重什么? #
11953次浏览 97人参与
# 如果能重来,就业or读研你选哪个? #
27550次浏览 227人参与
# 如何一边实习一边秋招 #
934229次浏览 12057人参与
# 网易求职进展汇总 #
20676次浏览 167人参与
# 软开人,秋招你打算投哪些公司呢 #
33852次浏览 400人参与
# 如何看待offer收割机的行为 #
500328次浏览 4915人参与
# 反问环节如何提问 #
58310次浏览 1498人参与
# 如果实习可以转正,你会不会放弃秋招 #
185939次浏览 2639人参与
# 实习与准备秋招该如何平衡 #
630133次浏览 7619人参与
# 应届生应该先就业还是先择业 #
42577次浏览 251人参与
# 简历无回复,你会继续海投还是优化再投? #
42071次浏览 525人参与
# 非技术投递记录 #
409136次浏览 5417人参与
# 远程面试的尴尬瞬间 #
10064次浏览 167人参与
# 你会选择考研还是直接就业 #
159664次浏览 1762人参与
# 如果可以,你希望哪个公司来捞你 #
25635次浏览 165人参与