数据结构与算法 / 系统课时

前缀函数

前缀函数

前缀函数把模式串每个位置之前的“可复用匹配长度”预先记录下来。掌握它后,你可以在字符失配时直接跳回仍可能成立的边界,而不必从头比较,这也是 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。

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));
    }
}

运行命令:

bash
javac PrefixFunctionDemo.java
java PrefixFunctionDemo

预期输出:

text
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) 前还要保证模式串非空,否则应由调用方提前处理。

本课练习

  1. 为模式串 aabaaab 手工计算前缀函数,再用程序验证。验收条件是每个位置都能指出对应的最长公共真前缀与真后缀。
  2. 修改示例,使程序逐行输出 i、当前字符、回退前的 j、回退后的 j 和最终 pi[i]。验收条件是 ababaca 的最终数组保持不变。

本课总结

  • pi[i] 保存子串 pattern[0..i] 的最长边界长度。
  • 失配时通过 pi[j - 1] 沿边界链回退,不能简单执行 j--。
  • 指针的累计移动受模式串长度限制,因此构建过程为 O(m)。

下一课预告

下一课将学习“KMP 匹配算法”,把前缀函数用于文本扫描,在不回退文本指针的前提下完成线性时间字符串匹配。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

前缀函数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通