1. 从暴力匹配的困境说起：为什么需要KMP？

如果你写过字符串匹配的代码，大概率是从最朴素的暴力匹配（Brute-Force）开始的。它的逻辑简单直接：将模式串（Pattern）的第一个字符与主串（Text）的第一个字符对齐，然后逐个字符向后比较。一旦发现不匹配，就将模式串整体向后滑动一位，再从头开始比较。这个过程就像拿着一把尺子，一格一格地在主串上移动比对。

这个算法在大多数情况下没问题，但它的效率瓶颈在于“回溯”。每次匹配失败，模式串只向后移动一位，而主串的指针（我们通常用i表示）和模式串的指针（用j表示）都需要回退。i会回退到本次匹配起始位置的下一位，j则直接回退到模式串的开头。想象一下，当主串是“aaaaaaaaab”，模式串是“aaab”时，暴力匹配会陷入一场灾难：前三个字符‘a’都能匹配上，到第四个字符时，主串是‘a’而模式串是‘b’，匹配失败。然后模式串右移一位，i回退到第二个字符，j回退到开头，再次重复前面三个‘a’的匹配……这种大量的、不必要的回溯导致了算法的时间复杂度高达 O(m*n)，其中 m 和 n 分别是主串和模式串的长度。

那么，有没有一种方法，能在匹配失败时，让主串的指针i不回溯，同时让模式串的指针j能智能地跳转到一个新的位置，而不是每次都傻傻地回到开头呢？这就是 KMP（Knuth-Morris-Pratt）算法要解决的核心问题。它通过一个被称为“部分匹配表”（Partial Match Table）或“Next 数组”的预处理器，记录了模式串自身的结构信息，从而在匹配失败时指导j进行高效跳转。而构建这个表的关键，正是理解标题中的核心概念——最大公共前后缀长度。可以说，吃透了它，你就掌握了 KMP 算法的灵魂。

2. 拆解核心概念：前缀、后缀与“最大公共”

要理解 KMP，必须先厘清几个基础但至关重要的定义。很多人在这里犯晕，导致后续学习如同雾里看花。

前缀（Prefix）：指一个字符串除了最后一个字符以外，所有以第一个字符开头的连续子串。 以字符串“ababa”为例：

• 长度为 1 的前缀：“a”
• 长度为 2 的前缀：“ab”
• 长度为 3 的前缀：“aba”
• 长度为 4 的前缀：“abab”注意，字符串本身（“ababa”）不是它的前缀，这是很多初学者容易混淆的点。前缀必须“严格地”不包含最后一个字符。

后缀（Suffix）：指一个字符串除了第一个字符以外，所有以最后一个字符结尾的连续子串。 同样以“ababa”为例：

• 长度为 1 的后缀：“a”
• 长度为 2 的后缀：“ba”
• 长度为 3 的后缀：“aba”
• 长度为 4 的后缀：“baba”同理，字符串本身（“ababa”）也不是它的后缀。后缀必须“严格地”不包含第一个字符。

公共前后缀：对于一个字符串的某个子串（通常我们考虑从开头到某个位置j的子串P[0…j]），如果存在一个子串，它既是这个子串的前缀，又是这个子串的后缀，那么这个子串就是一个公共前后缀。 还是看“ababa”，我们考虑它的前 5 个字符（即它本身）：

• 它的前缀有：“a”,“ab”,“aba”,“abab”
• 它的后缀有：“a”,“ba”,“aba”,“baba”
• 对比发现，“a”和“aba”同时出现在了前缀集合和后缀集合中。所以，“a”和“aba”都是“ababa”的公共前后缀。

最大公共前后缀长度：顾名思义，就是所有公共前后缀中，长度最长的那个的长度。注意，这里定义的是“长度”，而不是那个子串本身。 对于“ababa”，它的公共前后缀有“a”（长度 1）和“aba”（长度 3）。那么最长的就是“aba”，其长度为 3。因此，字符串“ababa”的最大公共前后缀长度就是3。

这里有一个极其特殊且重要的边界情况需要考虑：一个字符串的最大公共前后缀长度可以是 0，但绝不能是它自身的长度。因为根据定义，前缀和后缀都不能是字符串本身。例如，字符串“abcd”，它没有任何一个非空的子串同时是自己的前缀和后缀，所以它的最大公共前后缀长度是 0。而像“aaaa”这样的字符串，它的公共前后缀有“a”（长度1）、“aa”（长度2）、“aaa”（长度3），其中最长的是“aaa”，长度为3，而不是4。

注意：在 KMP 的语境下，我们通常不是一次性求整个模式串的最大公共前后缀长度，而是要求出模式串每一个前缀子串（从P[0]到P[j]，j从 0 到 m-1）的最大公共前后缀长度。这一系列长度值，就构成了我们构建 Next 数组的基础数据。理解这一点，是从概念过渡到实战的关键。

3. 手动计算实战：一步步推导 Next 数组

理论说再多，不如亲手算一遍。我们以一个经典的模式串“ababc”为例，来完整演示如何为它的每一个前缀子串计算最大公共前后缀长度，并最终得到 Next 数组。

首先明确，我们为模式串P的每个位置j（从 0 开始索引）计算一个值next[j]。这个值的定义在不同资料中略有差异，最常见的一种定义是：当模式串中第j个字符与主串不匹配时，下一步需要将模式串指针j跳转到的新的位置。而这个新位置，与当前子串P[0…j-1]的最大公共前后缀长度直接相关。

为了更直观地理解跳转，我更喜欢从“已匹配部分”的角度来思考。假设我们在匹配过程中，在模式串的第j位失败了，这意味着模式串的前j位（P[0…j-1]）已经和主串的某一段成功匹配了。那么，我们下一步要做的，就是利用这已匹配的j个字符的信息，找到一个新的起始点，使得模式串的前缀能够对准主串中这段已匹配内容的后缀，从而让主串指针i不用回溯，继续向前。

而这个“新的起始点”，就是P[0…j-1]这个子串的最大公共前后缀的长度。因为这个长度值，恰好指示了已匹配部分中，有多大一段前缀和后缀是相同的。既然相同，我们就可以把模式串的开头直接滑动到与这段后缀对齐的位置，从而跳过不可能成功的匹配尝试。

现在，我们来为P = “ababc”计算：

1. j = 0， 子串P[0…-1]不存在或为空串。空串的最大公共前后缀长度定义为 -1。这是一个特殊约定，用于处理模式串第一个字符就不匹配的情况（此时j已经为 0，无法再往前跳，需要移动模式串本身，即i++）。所以next[0] = -1。

2. j = 1， 考虑子串P[0…0] = “a”。

   • 前缀集合（除最后一个字符‘a’）：{空串} （因为长度为1的字符串，去掉最后一个字符就只剩空串）
   • 后缀集合（除第一个字符‘a’）：{空串}
   • 公共前后缀：只有空串。
   • 最大公共前后缀长度 = 0。
   • 所以next[1] = 0。含义：当P[1]（即‘b’）匹配失败时，j应该跳转到 0 的位置（即‘a’）去继续比较。

3. j = 2， 考虑子串P[0…1] = “ab”。

   • 前缀：“a”
   • 后缀：“b”
   • 公共前后缀：无（“a”不等于“b”）。
   • 最大公共前后缀长度 = 0。
   • 所以next[2] = 0。

4. j = 3， 考虑子串P[0…2] = “aba”。

   • 前缀：“a”,“ab”
   • 后缀：“a”,“ba”
   • 公共前后缀：“a”（长度1）。“ab”和“ba”不相等。
   • 最大公共前后缀长度 = 1。
   • 所以next[3] = 1。含义：当P[3]（即第二个‘a’）匹配失败时，j应该跳转到 1 的位置（即‘b’）去继续比较。为什么是1？因为已匹配的“ab”中，长度为1的前缀“a”和长度为1的后缀“a”相同，所以我们可以直接把模式串开头对齐到这个后缀上。

5. j = 4， 考虑子串P[0…3] = “abab”。

   • 前缀：“a”,“ab”,“aba”
   • 后缀：“b”,“ab”,“bab”
   • 公共前后缀：“ab”（长度2）。“a”和“b”不等，“aba”和“bab”不等。
   • 最大公共前后缀长度 = 2。
   • 所以next[4] = 2。

因此，对于模式串“ababc”，我们计算得到的 Next 数组为：[-1, 0, 0, 1, 2]。

实操心得：手动计算时，一定要严格按照“前缀集合”和“后缀集合”的定义来列写，并逐个比较。对于短串，可以快速心算；对于稍长的串，在纸上列出前后缀集合是避免出错的最好方法。很多同学出错，就是因为凭感觉猜测，忽略了“前后缀不能是字符串本身”这个严格规定。

4. Next数组的代码实现：递推与优化

理解了手工计算过程，我们来看如何用代码高效地生成 Next 数组。这是一个典型的动态规划或递推过程，核心思想是利用已知的next[0…j-1]来求解next[j]。

我们定义两个指针：i和j（注意，此处的i和j与主匹配函数中的含义不同，这里是构建 Next 数组的内部指针）。

• i：指向当前待计算next值的位置（即后缀的末尾）。
• j：指向前缀的末尾，同时也隐含了“当前已匹配的前缀长度”这一信息。初始时，next[0] = -1，i = 0，j = -1。

算法的核心递推关系如下：

1. 如果j == -1（意味着即将从头开始匹配），或者P[i] == P[j]（意味着当前字符可以扩展公共前后缀），那么next[++i] = ++j。即，公共前后缀长度增加 1。
2. 如果P[i] != P[j]，则匹配失败。此时，我们不将i回溯，而是让j利用已经计算好的next[j]进行回退，即j = next[j]。这一步是 KMP 思想在构建 Next 数组自身的体现，也是整个算法最精妙的地方。

以下是“ababc”的 Next 数组构建代码（C++风格）及逐步分析：

void getNext(const string& pattern, vector<int>& next) { int m = pattern.size(); next.resize(m); next[0] = -1; // 初始化 int i = 0; // 后缀末尾指针 int j = -1; // 前缀末尾指针，也代表 next[i] 的值 while (i < m - 1) { // 注意循环条件，因为 next[i] 赋值给的是 i+1 的位置 if (j == -1 || pattern[i] == pattern[j]) { // 情况1：可以扩展公共前后缀 ++i; ++j; next[i] = j; // 记录 P[0...i] 的最大公共前后缀长度为 j } else { // 情况2：匹配失败，j 回退 j = next[j]; } } }

我们来模拟一下这个过程，看它是如何得到[-1, 0, 0, 1, 2]的：

1. 初始：i=0,j=-1,next[0]=-1。
2. i=0,j=-1，满足j==-1，执行++i=1,++j=0,next[1]=0。
3. 现在i=1,j=0。比较P[1]=‘b’和P[0]=‘a’，不相等。执行j = next[0] = -1。
4. i=1,j=-1，满足j==-1，执行++i=2,++j=0,next[2]=0。
5. 现在i=2,j=0。比较P[2]=‘a’和P[0]=‘a’，相等。执行++i=3,++j=1,next[3]=1。
6. 现在i=3,j=1。比较P[3]=‘b’和P[1]=‘b’，相等。执行++i=4,++j=2,next[4]=2。
7. 循环结束。得到next = [-1, 0, 0, 1, 2]。

Next 数组的优化（Nextval 数组）基础的 Next 数组已经能工作，但存在一个可以优化的点。考虑模式串“aaaab”和主串“aaabaaaab”的匹配。当j=3（指向第四个‘a’）匹配失败时，next[3]=2，会跳转到第三个‘a’继续比较，而第三个‘a’显然也会失败，接着next[2]=1,next[1]=0，需要多次回退才能到正确的字符‘b’。这产生了不必要的比较。

优化的思路是：在构建 Next 数组时，如果发现回退后的字符与当前字符相同，那么这个回退是无效的，应该直接回退到那个字符的next值。即next[i] = next[j]。

优化后的代码（生成 Nextval 数组）如下：

void getNextVal(const string& pattern, vector<int>& nextval) { int m = pattern.size(); nextval.resize(m); nextval[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || pattern[i] == pattern[j]) { ++i; ++j; // 优化点：如果回退后的字符相同，则直接取回退位置的next值 if (pattern[i] != pattern[j]) { nextval[i] = j; } else { nextval[i] = nextval[j]; } } else { j = nextval[j]; } } }

对于“aaaab”，优化后的 Nextval 数组可能是[-1, -1, -1, -1, 3]，这样在匹配失败时能一步跳转到更远的位置，效率更高。在实际面试和工程中，理解并能手写基础的 Next 数组构建算法是必须的，如果能进一步解释 Nextval 的优化思想，则是大大的加分项。

5. 将Next数组应用于匹配：理解指针跳转的实质

有了 Next 数组，KMP 的主匹配算法就非常清晰了。它的核心逻辑与构建 Next 数组的过程惊人地相似，这体现了算法设计的一致性美。

主算法同样维护两个指针：i用于遍历主串T，j用于遍历模式串P。初始时i=0,j=0。

int kmpSearch(const string& text, const string& pattern, const vector<int>& next) { int n = text.size(), m = pattern.size(); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || text[i] == pattern[j]) { // 当前字符匹配成功，或 j 已回溯到开头 ++i; ++j; } else { // 当前字符匹配失败，j 根据 next 数组回退 j = next[j]; } } if (j == m) { // 模式串全部匹配成功 return i - j; // 返回匹配起始位置 } else { return -1; // 未找到 } }

让我们结合一个具体例子，看看 Next 数组是如何指导匹配的。设主串T = “abababc”，模式串P = “ababc”，其 Next 数组为[-1, 0, 0, 1, 2]。

1. 初始：i=0,j=0。T[0]=‘a’等于P[0]=‘a’，i++,j++->i=1,j=1。
2. T[1]=‘b’等于P[1]=‘b’，i++,j++->i=2,j=2。
3. T[2]=‘a’等于P[2]=‘a’，i++,j++->i=3,j=3。
4. T[3]=‘b’等于P[3]=‘b’，i++,j++->i=4,j=4。
5. 关键步骤：T[4]=‘a’不等于P[4]=‘c’。匹配失败。此时，j根据next[4]=2回退到j=2。注意，主串指针i=4纹丝不动！
6. 现在比较T[4]=‘a’和P[2]=‘a’，相等，i++,j++->i=5,j=3。
7. 比较T[5]=‘b’和P[3]=‘b’，相等，i++,j++->i=6,j=4。
8. 比较T[6]=‘c’和P[4]=‘c’，相等，i++,j++->i=7,j=5。此时j == m，匹配成功，返回i - j = 7 - 5 = 2。

为什么j回退到 2 是合理的？因为在失败那一刻，我们已经成功匹配了模式串的前 4 个字符“abab”。这个子串“abab”的最大公共前后缀是“ab”，长度为 2。这意味着，已匹配的主串片段“abab”的最后 2 位“ab”，与模式串开头的 2 位“ab”是相同的。因此，我们可以安全地将模式串向右滑动，使其开头的“ab”对齐到主串中已匹配片段末尾的“ab”上。这个对齐操作，在代码中体现为j回退到next[j]（即 2），而i保持不变。这样，我们跳过了所有已知不可能成功的匹配位置，实现了高效滑动。

6. 常见误区与深度思考

在理解和实现 KMP 时，有几个坑几乎每个人都会踩一遍。我把它们总结出来，希望能帮你绕过去。

误区一：Next 数组的定义不统一这是最混乱的一点。有的教材定义next[j]为当P[j]不匹配时，j应该跳转到的下一个位置索引（即我们上文使用的定义）。有的则定义它为P[0…j-1]这个子串的最大公共前后缀长度。这两者其实是等价的，因为“最大公共前后缀长度”的值，恰好就是跳转后j的新索引值（从0开始计数）。但在编码时，如果初始化next[0] = 0（表示长度为0），那么后续的递推和匹配逻辑都需要做相应调整。我强烈建议采用next[0] = -1的定义，它在逻辑上更清晰，代码也更简洁（可以用while (i < n && j < m)统一循环条件，并用j == -1作为特殊判断）。

误区二：忽略边界条件

• 空串和单字符串：模式串为空或长度为1时，Next 数组如何定义？匹配函数如何处理？这是代码鲁棒性的体现。对于空串，直接返回 0 或 -1 取决于业务定义。对于单字符串，next[0] = -1，匹配过程就是简单的遍历比较。
• 匹配成功后的继续查找：标准的 KMP 函数找到第一个匹配位置就返回了。如果需要找出所有匹配位置，在j == m匹配成功后，不能简单返回，而应该记录位置，然后执行j = next[j]（注意不是j=0！）来继续寻找下一个可能的匹配。因为已匹配的后缀可能同时也是下一个匹配的前缀。

误区三：对“部分匹配”价值的理解流于表面很多人只记住了“利用已匹配信息”，但没想透其本质。KMP 的高效，源于它对模式串进行了预处理，提取了其内在的“自相似性”信息（即 Next 数组）。这种预处理思想在算法设计中极其重要，比如在状态机、编译原理的词法分析中都有广泛应用。它用空间（O(m) 的 Next 数组）换时间，将匹配过程的时间复杂度降到了O(n+m)，其中 n 是主串长度。在模式串固定且需要多次匹配不同主串的场景下（如文本编辑器的查找功能），这种预处理的优势是巨大的。

误区四：死记硬背代码，不理解递推“能看懂，但自己写不出来”是常态。破解之法就是彻底理解 Next 数组的递推构建过程。你可以把它看作一个“自己匹配自己”的过程。指针i和j的移动，就是在寻找模式串前缀和后缀的重叠关系。j = next[j]这一行，是整个算法的灵魂，它意味着“在当前最长匹配前缀的后缀中，寻找次长的匹配前缀”。多画图，多模拟几个例子，直到你能在白板上无注释地写出getNext函数。

7. 从KMP到更广阔的字符串匹配世界

理解了 KMP，你就掌握了处理字符串匹配问题的一把利器。但 KMP 并非终点，它引向了一个更丰富的算法家族。

BM（Boyer-Moore）算法：这是在实际软件（如文本编辑器、IDE）中应用更广泛的算法，它比 KMP 更快。BM 算法的核心思想是“从后往前”匹配模式串，并利用“坏字符规则”和“好后缀规则”进行跳跃，其平均时间复杂度可以低于 O(n)，在某些情况下跳跃幅度非常大。学习 BM 算法，能让你体会到与 KMP 不同的设计哲学：KMP 是“前缀匹配失败，利用已知成功的前缀信息”，而 BM 是“后缀匹配失败或成功，利用整个模式串的信息进行更大胆的跳跃”。

Sunday 算法：一个更简单、也常被提及的算法。它关注的是主串中参与匹配的字符后一位的字符。如果这个字符不在模式串中，则直接跳过一大段；如果在，则对齐到模式串中该字符最后出现的位置。Sunday 算法实现简单，在随机文本中效率很高，是面试中除了 KMP 之外的一个不错谈资。

RK（Rabin-Karp）算法：利用哈希（Hash）技术。它将模式串的哈希值与主串中所有等长子串的哈希值进行比较。如果哈希值相同，再逐字符验证以避免哈希冲突。它的优势在于可以扩展到多模式匹配（如同时找多个关键词）和二维模式匹配。

Trie 树和 AC 自动机：当需要同时匹配多个模式串时，KMP 就力不从心了。AC 自动机可以看作是 KMP 算法在多模式串上的扩展。它首先将所有模式串构建成一棵 Trie 树，然后在 Trie 树上为每个节点建立“失败指针”（Fail Pointer），这个失败指针的思想与 KMP 的 Next 数组如出一辙，都是在匹配失败时进行状态跳转。AC 自动机是搜索引擎、敏感词过滤等系统的核心算法之一。

回过头看，KMP 算法中“最大公共前后缀长度”这个概念，不仅是解决单模式匹配的钥匙，其蕴含的“利用已知信息避免重复比较”的思想，更是贯穿了许多高级算法。下次当你被字符串匹配问题困扰时，不妨先想想：这个问题有没有“自相似”的结构？能不能通过预处理来加速？这种思维方式的训练，其价值远超过记住一个算法本身。我在处理复杂日志分析、数据流模式检测时，无数次地从 KMP 的思想中获得启发，去设计更高效的状态转移逻辑。