数据结构与算法 / 系统课时
前缀函数
前缀函数
前缀函数把模式串每个位置之前的“可复用匹配长度”预先记录下来。掌握它后,你可以在字符失配时直接跳回仍可能成立的边界,而不必从头比较,这也是 KMP 算法能够达到线性时间的关键准备。
学习目标
- 准确定义真前缀、真后缀与边界。
- 独立构建模式串的前缀函数数组。
- 理解失配回退规则与线性复杂度来源。
问题定义
对于字符串 pattern,前缀函数 pi[i] 表示子串 pattern[0..i] 中,最长的、同时是前缀和后缀的真子串长度。“真”表示不能取整个子串本身,因此 pi[0] 必定为 0。
以 ababaca 为例,位置 i = 4 对应子串 ababa。它的最长公共真前缀与真后缀都是 aba,长度为 3,所以 pi[4] = 3。位置 i = 5 加入字符 c 后,已有边界无法延伸,最终回退到 0。
核心原理与执行过程
计算 pi[i] 时,先令 j = pi[i - 1],把上一位置的最长边界作为候选。如果 pattern[i] 与 pattern[j] 相同,就能把边界延长一位;如果不同,则把 j 更新为 pi[j - 1],继续尝试更短但仍合法的边界。
这种回退不是随意减一。pi[j - 1] 已经记录了候选前缀内部的下一条最长边界,因此每次跳转都保留了“前缀等于后缀”的必要条件。

虽然 while 循环可能在某个位置连续回退,但指针 j 的总增长与总回退次数都受字符串长度约束。构建长度为 m 的模式串时,时间复杂度为 O(m),空间复杂度为 O(m)。
完整可运行示例
下面的 Java 17 程序构建前缀函数,并输出模式串与完整数组。将文件保存为 PrefixFunctionDemo.java。
import java.util.Arrays;
public class PrefixFunctionDemo {
static int[] buildPrefixFunction(String pattern) {
int[] pi = new int[pattern.length()];
for (int i = 1; i < pattern.length(); i++) {
int j = pi[i - 1];
// 失配时沿已知边界链回退,而不是重新从下标 0 比较。
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
// 当前字符能够接在候选边界之后时,边界长度增加一位。
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
pi[i] = j;
}
return pi;
}
public static void main(String[] args) {
String pattern = "ababaca";
int[] pi = buildPrefixFunction(pattern);
System.out.println("pattern = " + pattern);
System.out.println("pi = " + Arrays.toString(pi));
}
}运行命令:
javac PrefixFunctionDemo.java
java PrefixFunctionDemo预期输出:
pattern = ababaca
pi = [0, 0, 1, 2, 3, 0, 1]验证、Tips 与常见错误
验证前缀函数时,可以逐个位置取出 pattern[0..i],检查长度为 pi[i] 的前缀和后缀是否完全相同,并确认不存在更长的合法边界。调试回退逻辑时,重点打印 i、j 和 pi[j - 1],比只观察最终数组更容易定位问题。
常见错误是把 pi[i] 理解为“重复字符个数”。它描述的是连续边界长度,字符集合相同但顺序不同并不成立。另一个错误是在失配时执行 j--,这会尝试许多不具备边界性质的长度,既破坏逻辑,也可能退化为平方级比较。
空字符串的前缀函数可以定义为空数组;非空字符串必须从 i = 1 开始,因为 i = 0 没有非空真前缀。访问 pattern.charAt(j) 前还要保证模式串非空,否则应由调用方提前处理。
本课练习
- 为模式串
aabaaab手工计算前缀函数,再用程序验证。验收条件是每个位置都能指出对应的最长公共真前缀与真后缀。 - 修改示例,使程序逐行输出
i、当前字符、回退前的j、回退后的j和最终pi[i]。验收条件是ababaca的最终数组保持不变。
本课总结
pi[i]保存子串pattern[0..i]的最长边界长度。- 失配时通过
pi[j - 1]沿边界链回退,不能简单执行j--。 - 指针的累计移动受模式串长度限制,因此构建过程为
O(m)。
下一课预告
下一课将学习“KMP 匹配算法”,把前缀函数用于文本扫描,在不回退文本指针的前提下完成线性时间字符串匹配。