导语

本篇内容研究字符串匹配问题，首先介绍字符串匹配问题，引出Brute-Force算法及其优化方法，最后深入详解KMP算法。文章结构如下（全文阅读需要30分钟左右）：

字符串匹配问题

1字符串匹配问题是什么

"字符串A是否为字符串B的子串?如果是的话出现在B的哪些位置?"该问题就是字符串匹配问题，字符串A称为模式串，字符串B称为主串。

2应用

字符串匹配应用很广泛，比如你想在一篇文章中找到某个关键字所在的位置，或者是你想在一份名单中找到某个名字是否出现等等

Brute-Force算法

1算法核心思想

Brute-Force算法简称BF算法(并不是Boy Friend),算法的核心思想跟名字一样粗暴，如下所示：

2python代码实现

假设n为主串长度，m为模式串长度。

每一轮字符串比较：最差的情况为模式串最后一个字与主串不同其他都相同（如模式串为AAB，主串对应部分为AAC），必须走完整个字符串才能得出结果，因此复杂度为O(m)。

所有轮字符串比较：最差的情况是移动到最后一次比较才寻找得到，总共需要n-m+1次，主串通常比模式串长很多，故Brute-Force时间复杂度为O(nm)

3算法优化思路

最坏的情况：

两个字符串是否相同的比较很难优化，只能逐字比较。然而比较的趟数是可以减少的，因此尽可能减少比较的趟数是算法优化的方向，也是KMP算法的核心思想。那么，让我们开始KMP算法的讲解。

KMP算法详解

KMP算法于1977年被提出，全称 Knuth–Morris–Pratt 算法，包含了三位前辈名字，分别是：Donald Knuth(K), James H. Morris(M), VaughanPratt(P)

1算法核心思想

如何减少匹配的趟数呢？其实在每一次匹配过程中，我们就能够判断后续几次匹配是否会成功，算法的核心就是每次匹配过程中推断出后续完全不可能匹配成功的匹配过程，从而减少比较的趟数，如图所示：

因此，第一次匹配过之后，就可以得出可以直接跳到第四趟再进行判断的结论了。因为第一次匹配的时候，前5个序列和主串相同，只需要对模式串进行分析，模式串出现了重复单元(即AB)，在第一次匹配失败后就可以直接跳跃到出现重复单元的位置。

2next数组

next数组实质上就是找出模式串中前后字符重复出现的个数，为了能够跳跃不可能匹配的步骤。

next数组的定义为：next[i]表示模式串A[0]至A[i]这个字串，使得前k个字符等于后k个字符的最大值，特别的k不能取i+i,因为字串一共才i+1个字符，自己跟自己相等毫无意义。

最终得到next数组为：

如何确定在移动过程中需要跳过多少步呢？下图更直观的体现了跳跃的过程：

对于上述红色部分的计算跳过长度的公式为跳过的趟数=匹配上字符串中间字符长度-重复字符串长度

跳过这些步骤后并非再从头开始匹配，而是从重复位置开始匹配：

最终，我们不难得出如下结论：

3python代码实现

1.首先建立KMP对象，初始化参数：

2.建立next数组：

第一种最简单的构建方案，时间复杂度为O(m平法)：

第二种构建方案，是一种递推的方式进行构建，时间复杂度为O(n+m):

考虑：如果next[0], next[1], ... next[x-1]均已知，那么如何求出 next[x] ？

我们已经知道next[x-1],标记next[x-1]=temp,则可以讨论A[temp]和A[x]的值，分2种情况讨论：

第一种情况：A[temp]等于A[x]，也就是说在前一个next结果上又多了一个字符串相同的长度，因此next[x]为next[x-1]+1

第二种：当A[temp]和A[x]不相等的时候，我们需要缩小temp,把temp变成next[temp-1]，直到A[temp]=A[x]为止。A[now]=A[x]时，就可以直接向右扩展了。

递推构建next数组代码如下：

3.检索过程代码：

4.测试代码：

作者原创，未经授权请勿转载