什么是KMP算法（Knuth-Morris-Pratt字符串搜索算法）？

作者：程序员和吴师兄

KMP算法内部涉及太多数学原理和知识。本文仅描述KMP算法的工作过程以及部分匹配表，下面介绍的数组❀。如果你明白了这三点，再看看其他关于KMP算法的文章，你一定会明白的。

请阅读以下文字说明并搭配视频动画~ 花七分钟了解KMP算法。 Prat字符串搜索算法，简称为KMP算法，通常用于查找文本字符串中模式字符串P的出现。该算法由S.m联合发表。由唐纳德·Knuth、沃恩·Pratt和詹姆斯·H·Morris于 1977 年提出，因此该算法以这三个人的姓氏命名。

唐纳德·Knuth这个名字听起来熟悉吗？没错，他还出现在之前的文章，这可能是解释Knuth洗牌算法最好的文章！下面直接给出

KMP算法的工作过程：

• 我们假设文本字符串S与位置i和模式字符串 P

的位置相匹配。 j = -1 即当前如果字符匹配成功（即S[i] == P[j]），则继续匹配下一个字符i++、j++；
如果 j != -1 并且当前字符匹配失败（即 S[i] != P[j]），则让 i 保持不变，j = next[j]。这意味着，如果存在不匹配，则模式字符串 P 相对于文本字符串 S 向右移动 j -

你不明白吗？现场观看动画！

Running process

Take the following image text string S and pattern string P as an example:

First list all substrings of pattern string P:

a

acaabababaababababababababa Then get all每个子串的前缀和后缀。前缀

指的是字符串中除最后一个字符之外的所有主要组合； 后缀指字符串中除第一个字符之外的所有尾部组合。

以第五列为例进行演示。

前缀是

aababaaba

后缀后缀♷❀ ab

因此该前后缀公共元素的最大长度是。

获取原始模式串P 的子串对应的每个前缀和后缀的公共元素 的最大长度表，如下所示。

根据最大长度表，找到以下数组：xm相当于“最大xm”。将整数右移一位，然后将初始值设置为 -1 。

好了，拿到下一个数组后，KMP算法的工作原理就很清楚了。

将模式序列 P 的字母与文本字符串 S 一一匹配。如果不匹配，模式字符串会向右移动。

如何移动？

例如，b 与文本字符串 c 不匹配。在模式字符串的下一个数组中查找不匹配的处的匹配值，这里是0，然后将索引为0的位置移动到不匹配的位置。