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

KMP算法核心笔记：前后缀本质与nextval实现

news 来源：原创 2025/8/26 22:11:32

KMP算法核心笔记：前后缀本质与nextval实现

核心疑问：为什么用「前后缀」而非「最大子串」？

1. 结构唯一性

前后缀限定在字符串首尾区域，最大子串可位于任意位置
只有前后缀能保证滑动后的有效对齐

2. 移动确定性

文本：A B A B A C
模式：A B A B|---| 最长公共前后缀AB（长度2）
滑动后对齐：
文本：A B A B A C
模式：    A B A B

算法效率
预处理复杂度：前后缀O(m) vs 最大子串O(m²)

3. 通过「拼图对齐」理解前后缀的作用

场景设定：拼图匹配游戏
假设你有一块形状特殊的拼图模块（模式串），需要在一大块基板（文本）上找到正确的位置。基板上有许多凹凸结构，只有完全匹配才能拼合成功。

第一步：暴力匹配的问题

传统方法（暴力算法）就像每次尝试从头开始滑动拼图：

从基板的第一个位置开始尝试对齐
发现某处凹凸不匹配时，将拼图向右移动 1格
重复以上步骤直到全部匹配
问题：每次只移动1格，即使已经匹配了大部分结构，仍要重新检查已知匹配的部分，效率低下。

第二步：KMP的优化思路——利用「已匹配部分的结构」

假设拼图模块有重复的凹凸结构（即前后缀重复），可以利用这些信息跳过无效尝试：

已匹配部分：基板上有一段凹凸与拼图的前5格完全匹配基板：A B A B A ? … 拼图：A B A B A C ^ 第6格不匹配
发现重复结构：已匹配的A B A B A中，前缀A B A和后缀A B A相同

聪明移动：直接将拼图向右滑动，让前缀A B A对齐基板的后缀A B A 基板：A B A B A ? … 拼图： A B A B A C

为什么必须是前后缀？
前缀代表拼图起始部分的形状
后缀代表基板上已匹配部分的末尾形状
只有前后缀相同时，才能保证滑动后已匹配部分的形状仍然对齐，无需重新检查
对比「最大相同子串」的缺陷(无需匹配最大字串前的内容，也就是因为是前缀前面没有东西，如果是最大字串的匹配移动后不能保证最大字串前的内容可以和需匹配的文本匹配)
假设拼图内部有一个更大的重复子串（但不是前后缀）：

拼图：X Y X Y Z X Y X Y |-----| |-----| 最大子串最大子串
问题：这个子串不在开头或结尾，滑动后无法保证对齐
结果：可能错过正确位置，或仍需重复检查

关键结论
前后缀是滑动对齐的「锚点」
只有利用前后缀的重复，才能保证滑动后已匹配部分的结构一致。

其他子串无法提供滑动依据
最大相同子串可能位于任意位置，无法确定安全滑动距离。

KMP的数学本质
通过预处理找到每个位置的最长前后缀重复长度（next数组），实现精准滑动。

可视化总结
文本：A B A B A B A C A B A B A C |-----| |-----| 已匹配部分滑动后利用前后缀对齐模式：A B A B A C |-----| |-----| 前缀（滑动前）后缀（滑动后）
效果：跳过中间3次无效尝试，直接定位到可能匹配的位置。

KMP三要素实现（下标从-1开始）

1. next数组生成（naxtVal优化版）

int[] computeNext(String pattern) {int[] next = new int[pattern.length()];next[0] = -1;int j = 0, k = -1;while (j < pattern.length() - 1) {if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {j++;k++;next[j] = (pattern.charAt(j) == pattern.charAt(k)) ? next[k] : k;//使用(pattern.charAt(j) == pattern.charAt(k))进行优化进化成nextVal} else {k = next[k];}}return next;
}

生成逻辑

next[j] = 已匹配部分pattern[0…j-1]的最长公共前后缀长度
当pattern[j] == pattern[k]时，避免重复比较（提前优化为nextval逻辑）

困惑点

1.j和k是什么？

k 是当前最长公共前后缀的末尾索引（即前缀末尾的位置）也可以理解为前后缀匹配长度
j 在++前是指计算前后缀匹配的指针，在++后就是计算的next 数组的索引

2.else中为什么写成k = next[k]而不是从k=0重新开始匹配？

原文链接

KMP算法最难理解的地方就在这里，为了方便说明，我换了一张图

如下，j和k准备比较下一个

很遗憾这个位置，无法使其成为长度为4的相同前后缀，那么根据代码只能执行k=next[k]了。这样画比较难受，我把前缀直接拿到下面来

有没有似曾相识的感觉？没错，好像是主串和目标串，但这不是原来的那个两个串。而是后缀作为了主串，前缀作为了目标串，好的，现在前缀（目标串）的索引为3的位置发生了不匹配，该怎么做？自然是让前缀（目标串）下标为1的位置（next[3]=1）与该不匹配处重新比较

好的，重新组装回去，毕竟这不是真的主串和目标串

现在if继续判断，当然满足，对应位置相同，那么继续i++，j++，于是next[9]=2，此时next数组全部赋值完成。

换句话说，就是和kmp算法本质一样，将这个abac看作一个pattern，这个pattern一开始是需要匹配abab，但是在匹配到aba时发现下一个匹配不了就根据前后缀进行回溯到具有最大相同前后缀的地方也就是这个a，继续匹配，但与之前不同的是，并不是匹配abac，而是只需要匹配ab就行，如果匹配失败就是0

2. KMP搜索算法

int kmpSearch(String text, String pattern, int[] nextval) {int i = 0, j = 0, count = 0;while (i < text.length()) {if (j == -1 || text.charAt(i) == pattern.charAt(j)) {i++;j++;} else {j = nextval[j];}if (j == pattern.length()) {count++;j = nextval[j - 1];}}return count;
}

对比示例：模式串ABAB

索引	字符	next	nextval
0	A	-1	-1
1	B	0	0
2	A	0	-1
3	B	1	0

匹配过程优化

原next数组在索引3失败需回退到1
nextval直接回退到-1（少一次比较）

关键总结

前后缀是滑动对齐的锚点，确保移动后保留最大有效信息
nextval通过预判重复字符，减少无效回退次数
从-1开始的实现优势：
统一文本指针和模式指针的移动逻辑
代码更简洁直观（j == -1作为起点标志）

// 完整调用示例
public static void main(String[] args) {String text = "ABABABAC";String pattern = "ABABAC";int[] nextval = computeNextVal(pattern);int count = kmpSearch(text, pattern, nextval);System.out.println("匹配次数：" + count); // 输出1
}