KMP算法

作者: sakura579 | 来源:发表于2020-08-29 00:02 被阅读0次

什么是KMP算法?
快速地从一个主串中找出一个相同的字串


黄色的叫模式串
蓝色的叫主串
快速地从上面的主串中找出一段与之相同的字串
注意强调 快速地


可以发现:



①箭头左边地部分 上下 模式串和主串 完全匹配


②模式串左右两端 有两个子串 它们是完全匹配的
左右两端都有AB子串 它们两个称为模式串的 公共前后缀

KMP核心:

直接移动模式串,使得其公共前后缀里 原先的前缀 直接移动到 后缀原先的位置

这样移动可以保证 当前比较指针 所在的位置 它左边的串 上下是匹配的


为什么呢?
因为公共前后缀是匹配的 移动之前指针左边的串上下是匹配的
所以把前缀移到后缀的位置 上下也是匹配的

❌标识的那个位置字符 与 主串 不匹配

这个时候 只需要找到❌之前的串 当中的 公共前后缀 , 然后往前移动 模式串 使得前缀 来到原来 后缀的位置

如果模式串中 有多对公共前后缀 , 要取最长的一对


找公共前后缀



只有这一对 且是最长的



发现模式串 已经 超过主串的范围了

判定 匹配失败 ,主串中不含有和 模式串 相同的 子串

找公共前后缀 : 找最长的 且长度要小于 比较指针左端长度的公共前后缀




在这个移动过程中 根本就不需要看主串



KMP算法
只研究模式串就够了
把模式串相关信息挖掘出来之后,用它就可以和任何 主串 进行匹配


注意: 模式串是从 数组下标1 开始存储的 0位置什么都没有存

当然也可以从数组下标0开始存(原理一样 , 只是 结果值相差一个位置)

这部分从1开始存的学校比较多
就采取了这种大多数人比较习惯的方式

假设可以和任何主串进行KMP算法,每一个位置都可能发生不匹配


假如第一个位置就发生不匹配,


假设第二个位置发生不匹配,



箭头左边的子串长度只有1
公共前后缀的长度要求小于子串的长度
那么公共前后缀的长度只能为0

类比公共前后缀不为0的情况
移动之后指针左边的长度 就是公共前后缀的长度

这里呢公共前后缀长度是0,移动之后落在模式串中指针左边的子串就为0

比较指针所指的位置 就是主串中发生不匹配的位置 我们叫它 当前位置

这种情况下: 拿模式串的1号位 与 主串中 当前位置进行比较

next数组 (下一步数组)

这个数组 指示了 如果发生不匹配时下一步该干什么

相关文章

  • KMP 专题整理

    KMP 学习记录 kuangbin专题十六——KMP KMP 学习总结 朴素 KMP 算法 拓展 KMP 算法(E...

  • 对KMP算法的一些理解

    最近学到KMP算法,下面讲讲对KMP算法的一些个人理解,希望对大家有帮助! 对于KMP算法的理解: 整个KMP算法...

  • KMP算法文章合集

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

  • 串的模式匹配算法

    KMP算法 算法匹配

  • 问答|KMP算法学习笔记

    问题 目录KMP是什么,做什么用的KMP算法的高效体现在哪如何KMP算法的next数组KMP的代码KMP的时间复杂...

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

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

  • 字符串匹配 - KMP算法

    前面我们介绍非常高效的 BM 算法,今天我们介绍另一个非常出名且高效的 KMP 算法。 KMP 算法思想 KMP ...

  • KMP算法及优化

    转载请注明出处: KMP算法及优化 今天看到同学在复习数据结构书上的KMP算法,忽然发觉自己又把KMP算法忘掉了,...

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

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

  • KMP算法

    KMP算法

网友评论

      本文标题:KMP算法

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