python3实现KMP算法进行字符串匹配图文详解

本文链接：https://blog.csdn.net/victor2code/article/details/108358903

最近遇到一个字符串内查找指定子字符串出现位置的算法问题，最后虽然用暴力匹配法解决了问题，但是时间效率非常差。看到网上说可以用KMP模式匹配算法进行优化，搜了很多资料才基本弄懂，这里记录一下自己的理解和实现代码。

本文并没有重复造轮子，是基于结尾处两篇大神的参考文章的一些自我理解。大神的文章深入浅出通俗易懂，建议先行食用。

文章目录

实现效果

实现的效果类似于python中字符串的find方法

m='this is a great world'
m.find('great')
Out[43]: 10
m.find('nice')
Out[44]: -1

在m字符串中查找子字符串great出现的位置，最后返回的下标是10，也就是g出现的位置。而如果没有找到，返回-1。

暴力匹配的缺点

为了便于表述，将被匹配的字符串称为主字符串，长度设定为m，指针为i，用来匹配的字符串称为子字符串，长度设定为n，指针为j。

查找子串出现的位置，很容易就想到暴力匹配的方法，从主字符串下标0开始，对子字符串的每个元素依次进行匹配，如果不满足就移到下标1，重复匹配。一直到下标m-n+1如果还没找到说明肯定找不到了，这时候重复匹配才结束，所以最坏时间复杂度为O((m-n+1)*n)。

很显然这里的两个指针i和j一直在主字符串和子字符串上反复移动，消耗了大量时间，但是这种来回移动是没有必要的。

看下面的例子。

主字符串abacdef，子字符串为abab。当进行第一次匹配的时候，i移动到下标为3的c，j也移动到下标为3的b，此时对应的元素不相等。按照暴力匹配的方式，此时i要回到1，而j要回到0，重新开始匹配。

但是i和j真的有必要回去吗？

先看主字符串的指针i，因为已经知道下标为1的元素b肯定和子字符串的第一个元素a不同，那么就没有必要再比较了，而下标为2的元素a肯定和子字符串第一个元素a相同，也没有必要重复比较一次，所以i完全可以不用变。同样的对于子字符串的指针j，因为已经知道前一个字符a和开头的字符a相同，似乎直接回到下标为1的元素继续匹配就行。

所以简单的一分析就发现i根本不需要动，只需要将j从3移动到1就可以了，接下来用m[i]和n[j]继续比较。

我们这里只是感性地分析了一下，KMP算法则是真正用算法进行了实现。

KMP算法原理

最长前缀

首先针对字符串，有个前缀和后缀的概念要先理解清楚。前缀指的是从首个字符开始一直到任意一个非结尾字符组成的子字符串，例如xiaofu的前缀就可以是x,xi,xia,xiao,xiaof；后缀指的是从结尾字符开始往前一直到非开头字符的子字符串，例如xiaofu的后缀就可以是u,fu,ofu,aofu,iaofu。

而前缀和后缀的集合中相交的最长子字符串称之为最长前缀。例如字符串abacaba的前缀有a,ab,aba,abac,abaca,abacab，而后缀有bacaba,acaba,caba,aba,ba,a，交集只有aba，所以最长前缀也是aba

理解最长前缀是理解KMP算法的关键，因为不管i和j在什么位置，对于已经成功匹配的部分，主字符串和子字符串的内容相同，针对这部分内容，如果没有最长前缀，则说明i不用变（回去了也不可能有匹配）直接j变为0继续开始匹配。如果有最长前缀，那么最长前缀部分是可以跳过不用重复匹配的，i同样不用变（让j往前一点同样达到目的）j也不用变为0了。

下面用我自己的话来表述一下KMP算法的原则就是，主字符串的指针i永远不回溯，子字符串的指针j根据此时已匹配内容的最长前缀进行适当回溯。

例如下图中，当i=4和j=4时出现元素不相等的情况，此时i不变，而子字符串中0到j-1位置为前4个字符abab，最长前缀为2，其下一位也就是j=2的位置。之后从j=2和i=4继续比较，周而复始。