当前位置：首页 > news >正文

别再死记硬背了！用‘最长公共前后缀’口诀5分钟搞定KMP的next数组

news 2026/3/26 7:50:03

5分钟掌握KMP算法：用'最长公共前后缀'思维破解next数组难题

第一次接触KMP算法时，你是否也被那个神秘的next数组搞得晕头转向？作为字符串匹配领域的经典算法，KMP以其高效性著称，但next数组的计算过程却让无数初学者望而却步。传统教材中晦涩的公式和抽象的解释，往往让人陷入"看得懂但不会算"的困境。本文将带你用"最长公共前后缀"这一直观概念，彻底攻克next数组的计算难题。

1. 为什么需要next数组：从暴力匹配到KMP的进化

在了解next数组之前，让我们先看看最朴素的字符串匹配方法。假设我们要在文本串"ABABABCABAAB"中查找模式串"ABABC"，暴力匹配的做法是：

从文本串的第一个字符开始，逐个与模式串比较
遇到不匹配时，模式串整体右移一位，重新开始比较

这种方法在最坏情况下时间复杂度为O(mn)，其中m和n分别是模式串和文本串的长度。效率低下的原因在于，每次匹配失败后，模式串只移动一位，丢弃了之前已经匹配的部分信息。

KMP算法的精妙之处在于，它通过预处理模式串，构建next数组，记录匹配失败时模式串应该跳转的位置。这样，当字符不匹配时，文本串指针不需要回溯，模式串可以一次性移动多位，将时间复杂度降低到O(m+n)。

提示：next数组本质上记录了模式串自身的匹配信息，告诉我们当某个位置匹配失败时，模式串的前面有多少字符是可以"信任"的，不需要重新比较。

2. 最长公共前后缀：理解next数组的核心

next数组的计算核心在于"最长公共前后缀"（Longest Prefix Suffix，LPS）这一概念。对于模式串的每一个子串，我们需要找出其最长的相同前缀和后缀。

定义：

前缀：从字符串开头开始的连续子串（不包含最后一个字符）
后缀：以字符串结尾结束的连续子串（不包含第一个字符）
最长公共前后缀：既是前缀又是后缀的最长子串

例如，对于字符串"ABABC"：

子串"ABAB"的最长公共前后缀是"AB"（前缀"ABA"和后缀"BAB"的公共部分是"AB"）
子串"ABA"的最长公共前后缀是"A"（前缀"AB"和后缀"BA"的公共部分是"A"）

next数组的值就是该位置前子串的最长公共前后缀长度加1（假设数组从1开始索引）。这个"加1"是为了将长度转换为索引位置。

3. 手把手计算next数组：以"ABABAAABABAA"为例

让我们通过一个完整示例，一步步计算模式串"ABABAAABABAA"的next数组。为清晰起见，我们采用1-based索引（即第一个字符的索引为1）。

3.1 计算步骤详解

初始化：
- next[1] = 0（第一个字符没有前后缀）
计算next[2]：
- 子串："A"
- 最长公共前后缀：无（长度为0）
- next[2] = 0 + 1 = 1
计算next[3]：
- 子串："AB"
- 最长公共前后缀：无
- next[3] = 0 + 1 = 1
计算next[4]：
- 子串："ABA"
- 最长公共前后缀："A"（长度1）
- next[4] = 1 + 1 = 2
计算next[5]：
- 子串："ABAB"
- 最长公共前后缀："AB"（长度2）
- next[5] = 2 + 1 = 3
计算next[6]：
- 子串："ABABA"
- 最长公共前后缀："ABA"（长度3）
- next[6] = 3 + 1 = 4
计算next[7]：
- 子串："ABABAA"
- 最长公共前后缀："A"（长度1）
- next[7] = 1 + 1 = 2
继续计算剩余位置：
- 按照相同方法计算next[8]到next[12]

最终得到的next数组如下：

索引	1	2	3	4	5	6	7	8	9	10	11	12
字符	A	B	A	B	A	A	A	B	A	B	A	A
next	0	1	1	2	3	4	2	2	3	4	5	6

3.2 快速计算技巧

为了更高效地计算next数组，可以记住以下口诀：

首位置零：next[1] = 0
前后比较：从第二个字符开始，比较当前字符与前一个next值指向的字符
相同加一：如果相同，next值递增
不同回溯：如果不同，回溯到前一个next值的位置继续比较
归零重置：回溯到0仍不相同，则next值为1

这种方法避免了每次都重新计算最长公共前后缀，效率更高。

4. nextval数组：KMP算法的优化版本

虽然next数组已经能显著提升匹配效率，但在某些情况下还可以进一步优化，这就是nextval数组。nextval数组在next数组的基础上，消除了不必要的回溯。

4.1 nextval的计算规则

nextval数组的计算基于以下原则：

如果模式串的当前字符与next值指向的字符不同，则nextval值与next值相同
如果两者相同，则nextval值等于nextval[next[j]]

用公式表示为：

对于j > 1：

if (P[j] != P[next[j]]) { nextval[j] = next[j] } else { nextval[j] = nextval[next[j]] }

4.2 nextval计算示例

继续使用之前的"ABABAAABABAA"模式串和已计算的next数组：

初始化：
- nextval[1] = next[1] = 0
计算nextval[2]：
- P[2] = 'B', P[next[2]] = P[1] = 'A'
- 不相同 → nextval[2] = next[2] = 1
计算nextval[3]：
- P[3] = 'A', P[next[3]] = P[1] = 'A'
- 相同 → nextval[3] = nextval[next[3]] = nextval[1] = 0
计算nextval[4]：
- P[4] = 'B', P[next[4]] = P[2] = 'B'
- 相同 → nextval[4] = nextval[next[4]] = nextval[2] = 1
继续计算剩余位置...