字符串匹配算法

1.朴素算法
2.RK算法
3.kmp算法
详细讲解:
主要在于搜索字符串相对原字符串需要后移多少位.对比字符串与搜索字符串的第一个字符，若不相同，则讲搜索字符串向后移一位.若相同则对比两者的第二个字符串.当移动到第n个字符时,发现不相同，这是需要就算出部分匹配表,目的在于决定将搜索字符串后移多少位,若还是按老规矩只向后移一位,其实是效率低下的一种做法.因为此时已经知道前n-1个字符是什么了.
至于如何计算部分匹配表,与字符串前缀 后缀有关系.前缀和后缀字符串最长的共同的字符个数就是该字符的部分匹配值.


kmp.png

4.BM算法
5.Sunday算法

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 字符串匹配算法
    1、BF算法 假设现有一字符串，“BBC ABCDAB ABCDABCDABDE”将其称为给定串，相应有一匹配串“...
    橙小汁阅读 3,933评论 5赞 13
  • 字符串匹配算法
    KMP算法 算法介绍 KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。...
    九命丿相柳阅读 3,214评论 0赞 1
  • 字符串匹配算法（KMP）
    两个字符串A、B，在A字符串中查找B字符串（分别长为m,n），如果找到了，返回B字符串在A字符串中第一次出现的下标...
    Myth52125阅读 1,787评论 0赞 0
  • 字符串匹配算法之Sunday算法
    字符串匹配算法之Sunday算法 背景 我们第一次接触字符串匹配，想到的肯定是直接用2个循环来遍历，这样代码虽然简...
    houskii阅读 13,366评论 10赞 25
  • [全栈开发工程师]_Full Stack Developer
    1 全栈工程师是很多公司高薪聘请， 却找不到的人才。 2 全栈工程师有多年IT从业的经验， 对各个技术领域的知识都...
    Eric苏离阅读 3,056评论 0赞 0