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

前缀函数与模式匹配

前缀函数与模式匹配

KMP 的核心不是记住代码,而是理解失配后还能保留多少已匹配信息。本课先构建前缀函数,再用它让文本指针始终向前扫描,并支持查找重叠结果。

学习目标

  • 理解最长相等真前后缀及前缀函数
  • 掌握前缀表的扩展与回退过程
  • 使用 KMP 在线性时间内查找全部匹配位置

前缀函数的含义

对模式串 pattern,定义 prefix[i] 为子串 pattern[0..i] 的最长相等真前缀与真后缀长度。“真”表示不能取整个字符串本身。

例如 ABABA 的最长相等真前后缀是 ABA,长度为 3。这个长度表示:当前已匹配部分失配后,不必完全清零,仍可保留一个更短但已经验证过的模式前缀。

构建与匹配机制

计算 prefix[i] 时,先令候选长度为 prefix[i - 1]。若当前字符与候选前缀的下一个字符不相等,就反复回退到 prefix[matchedLength - 1];若相等,再把长度加一。

扫描文本时使用同样的回退规则。文本下标不后退,只调整“当前已匹配的模式长度”。当长度等于模式串长度时,匹配起点是 i - pattern.length() + 1。记录结果后继续按前缀表回退,便可发现重叠匹配。

KMP 前缀回退与匹配流程

完整示例

下面的 Java 17 程序构建前缀表,并返回文本中的全部匹配位置。

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PrefixFunctionMatchDemo {

    public static void main(String[] args) {
        String text = "ABABABABCABABABC";
        String pattern = "ABABABC";

        System.out.println("前缀表: "
            + Arrays.toString(buildPrefix(pattern)));
        System.out.println("匹配位置: " + findAll(text, pattern));
    }

    private static int[] buildPrefix(String pattern) {
        int[] prefix = new int[pattern.length()];

        for (int i = 1; i < pattern.length(); i++) {
            int matchedLength = prefix[i - 1];

            // 失配时回到仍可能成立的更短前缀
            while (matchedLength > 0
                && pattern.charAt(i) != pattern.charAt(matchedLength)) {
                matchedLength = prefix[matchedLength - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(matchedLength)) {
                matchedLength++;
            }
            prefix[i] = matchedLength;
        }
        return prefix;
    }

    private static List<Integer> findAll(String text, String pattern) {
        List<Integer> positions = new ArrayList<>();
        if (pattern.isEmpty()) {
            positions.add(0);
            return positions;
        }

        int[] prefix = buildPrefix(pattern);
        int matchedLength = 0;

        for (int i = 0; i < text.length(); i++) {
            while (matchedLength > 0
                && text.charAt(i) != pattern.charAt(matchedLength)) {
                matchedLength = prefix[matchedLength - 1];
            }
            if (text.charAt(i) == pattern.charAt(matchedLength)) {
                matchedLength++;
            }

            if (matchedLength == pattern.length()) {
                positions.add(i - pattern.length() + 1);
                // 不清零,保留可能形成重叠匹配的前缀
                matchedLength = prefix[matchedLength - 1];
            }
        }
        return positions;
    }
}

预期输出:

text
前缀表: [0, 0, 1, 2, 3, 4, 0]
匹配位置: [2, 9]

复杂度与边界

构建前缀表需要 O(m) 时间,扫描文本需要 O(n) 时间,总时间复杂度为 O(n + m),前缀数组占用 O(m) 空间。虽然代码中存在 while,但匹配长度在整个过程中增加和回退的总次数都是线性的。

前缀函数保存的是长度,不是字符下标,因此回退位置必须写成 prefix[matchedLength - 1]。本课约定空模式串返回位置 [0];业务系统也可以选择返回全部边界位置,但必须提前统一接口语义。

常见错误

失配时简单执行 matchedLength-- 会丢失前缀表提供的跳转信息。完整匹配后直接清零会遗漏重叠结果。KMP 的文本下标始终向前,不应退回已经扫描的位置;否则会破坏线性复杂度。

练习

使用文本 aaaaa 和模式 aaa 验证重叠匹配。完整匹配后按前缀函数回退,结果应为 [0, 1, 2]。

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

目录与阅读设置

阅读设置

17

记录一个想法

前缀函数与模式匹配

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

登录哪都通