一文读懂字符串之 KMP 算法

景禹 2020-08-19

1416

以前的计算机刚被发明的时候，主要作用是做一些科学和工程的计算工作，科学家发明计算机的时候压根儿不可能想到后人还可以用来KMP。

刚开始的计算机都是处理数值工作，后来引入了字符串的概念，计算机开始可以处理非数值的概念了（当然原理还是用数值来模拟非数值，通过ASCII码表）。

总之在工作当中字符串的处理操作非常普遍，今日主要分享字符串模式匹配算法KMP的相关操作。

在分享KMP算法之前，我们先看一下蛮力法进行模式匹配的过程：

显然蛮力法的执行效率太低了，为此有大佬提出了KMP算法。在详细介绍KMP算法之前，我们看一下字符串的前缀与后缀的概念：

有了字符串前缀与后缀的概念，我们就可以计算出一个字符串前缀与后缀的公共子串的最大长度。

此时，我们就可以来看KMP算法的执行过程了。

第一步：

第二步：

第三步：

第四步：

第五步：

理解KMP算法的执行过程中，一定要注意景禹在图片中标注的文字。最后我们来看一下动画演示：

今日给大家分享就到这里，有什么问题欢迎留言，景禹一定知无不言！

推荐阅读

数据结构与算法之递归+分治

END

作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。

文章转载自景禹，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。