一文读懂字符串之 KMP 算法

一文读懂字符串之 KMP 算法


以前的计算机刚被发明的时候,主要作用是做一些科学和工程的计算工作,科学家发明计算机的时候压根儿不可能想到后人还可以用来KMP。
刚开始的计算机都是处理数值工作,后来引入了字符串的概念,计算机开始可以处理非数值的概念了(当然原理还是用数值来模拟非数值,通过ASCII码表)。
总之在工作当中字符串的处理操作非常普遍,今日主要分享字符串模式匹配算法KMP的相关操作。
显然蛮力法的执行效率太低了,为此有大佬提出了KMP算法。在详细介绍KMP算法之前,我们看一下字符串的前缀与后缀的概念:
一文读懂字符串之 KMP 算法
有了字符串前缀与后缀的概念,我们就可以计算出一个字符串前缀与后缀的公共子串的最大长度。
一文读懂字符串之 KMP 算法
此时,我们就可以来看KMP算法的执行过程了。
第一步:
一文读懂字符串之 KMP 算法
第二步:
一文读懂字符串之 KMP 算法
第三步:


一文读懂字符串之 KMP 算法

第四步:
一文读懂字符串之 KMP 算法
第五步:
一文读懂字符串之 KMP 算法
理解KMP算法的执行过程中,一定要注意景禹在图片中标注的文字。