一文读懂字符串之 KMP 算法_吴师兄学算法-五分钟学算法

一文读懂字符串之 KMP 算法

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

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

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

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

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

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

第一步：

第二步：

第三步：

第四步：

第五步：

理解KMP算法的执行过程中，一定要注意景禹在图片中标注的文字。