什么是KMP算法?
快速地从一个主串中找出一个相同的字串
黄色的叫模式串
蓝色的叫主串
快速地从上面的主串中找出一段与之相同的字串
注意强调 快速地
可以发现:
①箭头左边地部分 上下 模式串和主串 完全匹配
②模式串左右两端 有两个子串 它们是完全匹配的
左右两端都有AB子串 它们两个称为模式串的 公共前后缀
KMP核心:
直接移动模式串,使得其公共前后缀里 原先的前缀 直接移动到 后缀原先的位置
这样移动可以保证 当前比较指针 所在的位置 它左边的串 上下是匹配的
为什么呢?
因为公共前后缀是匹配的 移动之前指针左边的串上下是匹配的
所以把前缀移到后缀的位置 上下也是匹配的
❌标识的那个位置字符 与 主串 不匹配
这个时候 只需要找到❌之前的串 当中的 公共前后缀 , 然后往前移动 模式串 使得前缀 来到原来 后缀的位置
如果模式串中 有多对公共前后缀 , 要取最长的一对
找公共前后缀
只有这一对 且是最长的
发现模式串 已经 超过主串的范围了
判定 匹配失败 ,主串中不含有和 模式串 相同的 子串
找公共前后缀 : 找最长的 且长度要小于 比较指针左端长度的公共前后缀
在这个移动过程中 根本就不需要看主串
KMP算法
只研究模式串就够了
把模式串相关信息挖掘出来之后,用它就可以和任何 主串 进行匹配
注意: 模式串是从 数组下标1 开始存储的 0位置什么都没有存
当然也可以从数组下标0开始存(原理一样 , 只是 结果值相差一个位置)
这部分从1开始存的学校比较多
就采取了这种大多数人比较习惯的方式
假设可以和任何主串进行KMP算法,每一个位置都可能发生不匹配
假如第一个位置就发生不匹配,
假设第二个位置发生不匹配,
箭头左边的子串长度只有1
公共前后缀的长度要求小于子串的长度
那么公共前后缀的长度只能为0
类比公共前后缀不为0的情况
移动之后指针左边的长度 就是公共前后缀的长度
这里呢公共前后缀长度是0,移动之后落在模式串中指针左边的子串就为0
比较指针所指的位置 就是主串中发生不匹配的位置 我们叫它 当前位置
这种情况下: 拿模式串的1号位 与 主串中 当前位置进行比较
next数组 (下一步数组)
这个数组 指示了 如果发生不匹配时下一步该干什么
