3. KMP算法(Knuth-Morris-Pratt)【参考文章:漫画:什么是KMP算法?;KMP算法—终于全部弄懂了_June·D的博客-CSDN博客】
回顾一下前两种算法效率不高的原因:在不匹配时 , 从待匹配串的起始位置重新全部开始匹配;反复计算哈希值 , 且需要处理哈希冲突的问题 。这两种方式可以看作每次将字符串向后一位一位滑动 。这样的方式导致了中间存在大量无意义的比较,以及不得不完成的比较,使得效率低下 。而KMP就针对这一点进行了优化,其核心在于:在匹配过程中,当不匹配时,对于已匹配好的部分,找到一种规律,将模式串一次性向后滑动很多位,从而提高效率 。其中,记不匹配的字符为 “坏字符” , 已匹配的部分为 “好前缀” 。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 于是现在的问题就:如何制定滑动策略?
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 接下来进一步思考滑动策略的细节:不匹配时,应当滑动到哪里?
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21a5J-35.png)
文章插图
首先,把主串和模式串的首位对齐,从左到右对逐个字符进行比较 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192S6-36.png)
文章插图
第一轮,发现前5个字符都是匹配的,第6个字符不匹配,将其标记为坏字符 ‘A’ 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194A3-37.png)
文章插图
【重难点】
可以发现,在好前缀 “GTGTG” 当中,主串的好前缀的后三个字符 “GTG” 和模式串的前三位字符 “GTG” 是相同的 。我们分别把这两部分记作可匹配后缀子串与可匹配前缀子串 。在之后的比较中,这两部分一定能够匹配上 。并且在这两个部分匹配上之前,一定没有其他可能使得模式串成功匹配的情况,这也为选择最长的子串进行滑动提供了保障 。因此,我们直接将模式串后移两位 , 使得这两部分对齐 , 并开始下一次比较 , 省去了中间的无效比较 。
同理 , 如果在好前缀中如果存在多个可匹配后缀子串 , 那么为了能省区更多的无效比较 , 我们选择找到最长的子串进行滑动 。因此,我们的滑动策略为:在主串的好前缀中,找到最长可匹配后缀子串;在模式串中,找到对应的最长可匹配前缀子串 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21aQ7-38.png)
文章插图
第二轮,我们直接把模式串向后移动两位,让两个 “GTG” 对齐,继续从刚才主串的坏字符 ‘A’ 开始进行比较 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194211-39.png)
文章插图
此时,主串的字符 ‘A’ 仍然是坏字符 , 这时候的匹配前缀缩短成了 “GTG” 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194242-40.png)
文章插图
按照第一轮的思路,我们来重新确定最长可匹配后缀子串和最长可匹配前缀子串 。此时,剩下字符串 “G” 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2191R5-41.png)
文章插图
第三轮,我们再次把模式串向后移动两位,让两个“G”对齐,继续从刚才主串的坏字符A开始进行比较 。
……
小结:整体思路是,在主串的好前缀中寻找最长可匹配后缀子串(在好前缀中,从后往前找),在模式串中寻找对应的最长可匹配前缀子串(在已匹配串中,从前往后找),直接把两者对齐 , 从而实现模式串的快速滑动 。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 知道了退回到哪里 , 现在的关键在于如何实现退回?【重难点】
推荐阅读
- 【前端必会】不知道webpack插件? webpack插件源码分析BannerPlugin
- 20220929-ArrayList扩容机制源码分析
- Optional源码解析与实践
- Go 源码解读|如何用好 errors 库的 errors.Is 与 errors.As() 方法
- .Net下的分布式唯一ID
- .NET 反向代理 YARP 代理 GRPC
- 赞美父亲的作文结尾 赞美父亲的高中作文
- 关于对自己有信心的名言名语 对学习有信心的名言
- 关于父亲的高中作文800字 关于父亲的高中作文
- 高一化学全面学习方法整理