美文网首页
KMP字符串匹配算法

KMP字符串匹配算法

作者: 云彩修建站站长 | 来源:发表于2019-10-14 11:32 被阅读0次

阮一峰的文章
字符串匹配算法:给定两个字符串A和B,问字符串A是否包含字符串B。

KMP算法

最简单的思路如下:

  1. 就是A字符串固定,然后把B字符串和A字符串对齐,从头到尾进行字符的比较。
  2. 遇到字符不相同的情况,将B字符串向后错一位。
  3. 一直比较直到比较完A和B为止。

这种思路是比较耗时的,很多比较都是浪费,所以才有了KMP算法,KMP这三个字母是三个大佬的首字母。KMP的思路如下:

  1. 构建《部分匹配表》,对于字符串B,每个字符都计算一个部分匹配值。
  2. 按照“简单思路”的1和2,进行匹配,但是遇到不相同的字符时,并不是将B字符串向后错一位。错位的数量为:匹配中的字符数 - 匹配中的最后一个字符的部分匹配值
  3. 一直比较直到比较完A和B为止。

KMP的思路就是,每次错位的时候,放弃掉无效的错位,直接把B字符串错位到最有可能进行匹配中的位置。

相关文章

  • KMP算法文章合集

    字符串的查找:朴素查找算法和KMP算法 暴力匹配算法与KMP算法(串的匹配) 字符串查找算法BF和KMP 字符串匹...

  • leetcode字符串匹配算法之KMP算法

    本篇介绍一种高效的字符串匹配算法——KMP算法。 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J....

  • 字符串匹配与KMP算法

    1.朴素字符串匹配算法 2.KMP算法 求前缀函数 实现KMP算法 3.测试代码

  • 常见算法题之字符串

    1、KMP算法 参考:july大神的KMP博客细节不摆,该算法由暴力字符串来匹配,具体是由字符串匹配的暴力写法而来...

  • KMP算法(字符串匹配问题)

    一、是什么? 注意,是KMP算法,不是MMP哈,我没有骂人。KMP算法是用来做字符串匹配的,除了KMP算法分,还有...

  • KMP算法——寻找子串位置

    KMP算法——寻找子串位置 1、KMP算法简介: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J....

  • KMP算法

    KMP算法是解决字符串匹配问题的有高效算法 代码:

  • KMP字符串匹配算法

    KMP字符串匹配算法 先总结一下之前的几种字符串匹配算法 1 BF算法, 最简单的字符串匹配算法, 可以直接使用s...

  • 09--KMP

    [toc] KMP算法原理 KMP思想 假设字符串abcdefgab和模式串abcdex,进行匹配,当匹配到x位置...

  • KMP算法理解

    文章大纲:1.KMP算法概念2.KMP算法中最核心的next[] 数组是如何生成的3.使用KMP算法 匹配字符串 ...

网友评论

      本文标题:KMP字符串匹配算法

      本文链接:https://www.haomeiwen.com/subject/bkzlmctx.html