知模式串为“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算法,我们可以高效地找到模式串在主串中的位置,避免了不必要的重复比较。
点赞 评论

相关推荐

面经:首先自我介绍,然后由面试官提问, 专业方面大部分是模电的基础,再问一些关于你生活的事情,以及你的工作意愿,最后再问有没有想要问的了。问题整理:场效应管的结构和用处二极管的组成和用途三极管的组成和用途有什么兴趣爱好愿不愿来华硕工作毕业设计的一些设计运用什么原理说说大学期间的一件付出了努力但没有得到相应回报的事?大学做的最有成就感的事?大学遇到过的最有挫折感的事?如果工作以后,离职可能是什么原因?总之面试官没有多严厉,还是让你别紧张,全程比较轻松。华硕ASUS 2025届校园招聘进行中【关于华硕】全球领先的3C解决方案提供商之一,产品线完整覆盖至笔记本电脑、主板、显卡、服务器等全线3C产品。华硕拥有遍布全球20多个国家和地区的分支机构,以及十万名员工,已成为年营业额超过165亿美元的信息产业巨擘【招聘岗位】主板硬件研发、商用电脑硬件研发、海外硬件研发、硬件工程师、C/C++软件工程师、Java开发工程师 (最多可投递3个岗位,可同时安排笔/面试)【工作城市】苏州【福利待遇】双休,六险二金,带薪年假/事假/病假/年度体检/节日福利等,专业技术培养体系【内推链接】https://asustek.zhiye.com/campus/jobs?shareId=5262df38-cd6f-4f1a-bf59-1dd761044408&shareSource=2【内推码】ESKPGJ(简历优先筛选,后续有疑问/流程问题欢迎联系)大家投递完可以在评论区打上姓名缩写+岗位,我来确认有没有内推成功喽
华硕科技(苏州)有限公司
|
校招
|
10个岗位
点赞 评论 收藏
分享
牛客网
牛客企业服务