每日算法 — 使用java实现字符串匹配：KMP前缀函数与线性时间模式搜索

在日常开发中，字符串匹配是最基础也最频繁出现的操作之一。无论是文本编辑器中的查找替换、搜索引擎的关键词高亮，还是生物信息学中的DNA序列比对，都需要高效地在一个长文本（主串）中定位某个模式串的出现位置。

暴力解法逐个字符比对，最坏情况下时间复杂度为 O(m×n)。而今天要介绍的 KMP算法（Knuth-Morris-Pratt）通过巧妙构建”前缀函数”，将匹配过程优化到 O(m+n) 的线性时间，是算法面试与工程实践中的经典必考点。

暴力匹配的问题在哪里

假设主串为 ABABABABC，模式串为 ABABC。暴力解法从左到右逐位比较，当遇到不匹配时，模式串只回退一位再重新开始比对。

在位置4发生不匹配时（主串A vs 模式串C），暴力解法不知道：模式串前4位ABAB与主串前4位完全一致。它浪费了已经获取的匹配信息，导致大量重复比较。

KMP的核心思想：利用已匹配信息

KMP算法的精髓在于 “永不回退主串指针”。当发生不匹配时，不是将模式串整体右移一位，而是根据已匹配的部分，计算出模式串应该跳到哪个位置继续比较。

这个”跳到哪个位置”的信息，就存储在 前缀函数（prefix function） 中，也叫 next数组。

什么是前缀函数

对于模式串的每个位置 i，前缀函数 π[i] 表示：子串 pattern[0..i] 中，真前缀与真后缀相等的最长长度。

真前缀：不等于自身的所有前缀。例如ABAB的真前缀有A、AB、ABA。

以模式串 ABABC 为例：

这个数组告诉我们：当在位置i发生不匹配时，模式串可以跳到 π[i-1] 的位置继续比较，而无需回退主串指针。

前缀函数的高效构建

前缀函数不是暴力计算，而是利用已计算的 π[0..i-1] 在 O(m) 内递推构建。

核心递推逻辑：
– 初始化 π[0] = 0
– 维护一个长度变量 k，表示当前匹配的前缀长度
– 对于每个新字符，如果 pattern[k] == pattern[i]，则 k++，π[i] = k
– 如果不等，则利用 π[k-1] 回退 k，直到匹配或 k=0

完整Java实现

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

/**
 * KMP字符串匹配算法完整实现
 * 时间复杂度：O(m + n)，其中 m 为模式串长度，n 为主串长度
 */
public class KMPMatcher {

    /**
     * 构建前缀函数（next数组）
     * @param pattern 模式串
     * @return 前缀函数数组
     */
    public static int[] buildPrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        // pi[0] 恒为 0，因为单个字符没有真前缀

        int k = 0; // 当前匹配的前缀长度

        for (int i = 1; i < m; i++) {
            // 当不匹配时，利用已计算的前缀函数回退
            while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
                k = pi[k - 1];
            }

            // 如果当前字符匹配，扩展匹配长度
            if (pattern.charAt(k) == pattern.charAt(i)) {
                k++;
            }

            pi[i] = k;
        }

        return pi;
    }

    /**
     * KMP搜索：返回模式串在主串中的所有匹配起始位置
     * @param text 主串
     * @param pattern 模式串
     * @return 所有匹配位置的列表（0-based）
     */
    public static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();

        if (pattern.isEmpty() || text.length() < pattern.length()) {
            return matches;
        }

        int[] pi = buildPrefixFunction(pattern);
        int k = 0; // 当前已匹配的模式串长度

        for (int i = 0; i < text.length(); i++) {
            // 不匹配时回退模式串指针
            while (k > 0 && (k >= pattern.length() || pattern.charAt(k) != text.charAt(i))) {
                k = pi[k - 1];
            }

            // 当前字符匹配
            if (pattern.charAt(k) == text.charAt(i)) {
                k++;
            }

            // 完全匹配
            if (k == pattern.length()) {
                matches.add(i - pattern.length() + 1);
                // 继续搜索：利用前缀函数允许重叠匹配
                k = pi[k - 1];
            }
        }

        return matches;
    }

    /**
     * 简化版KMP：只返回首次匹配位置，-1表示未找到
     */
    public static int indexOf(String text, String pattern) {
        List<Integer> matches = kmpSearch(text, pattern);
        return matches.isEmpty() ? -1 : matches.get(0);
    }

    /**
     * 可视化前缀函数，便于理解
     */
    public static void printPrefixFunction(String pattern) {
        int[] pi = buildPrefixFunction(pattern);
        System.out.println("模式串: " + pattern);
        System.out.print("下标  : ");
        for (int i = 0; i < pattern.length(); i++) {
            System.out.print(i + " ");
        }
        System.out.println();
        System.out.print("字符  : ");
        for (char c : pattern.toCharArray()) {
            System.out.print(c + " ");
        }
        System.out.println();
        System.out.print("π数组 : ");
        for (int v : pi) {
            System.out.print(v + " ");
        }
        System.out.println();
    }

    // 主程序：演示与测试
    public static void main(String[] args) {
        // 示例1：基础匹配
        String text1 = "ABABDABACDABABCABAB";
        String pattern1 = "ABABC";
        System.out.println("=== 示例1：基础匹配 ===");
        System.out.println("主串  : " + text1);
        System.out.println("模式串: " + pattern1);
        printPrefixFunction(pattern1);
        System.out.println("匹配位置: " + kmpSearch(text1, pattern1));
        System.out.println();

        // 示例2：重叠匹配
        String text2 = "AAAAA";
        String pattern2 = "AA";
        System.out.println("=== 示例2：重叠匹配 ===");
        System.out.println("主串  : " + text2);
        System.out.println("模式串: " + pattern2);
        System.out.println("匹配位置: " + kmpSearch(text2, pattern2));
        System.out.println();

        // 示例3：DNA序列比对场景
        String dna = "ATCGATCGATCGGCTA";
        String seq = "ATCG";
        System.out.println("=== 示例3：DNA序列匹配 ===");
        System.out.println("DNA序列: " + dna);
        System.out.println("目标片段: " + seq);
        System.out.println("匹配位置: " + kmpSearch(dna, seq));
        System.out.println();

        // 示例4：未找到的情况
        String text4 = "HELLO WORLD";
        String pattern4 = "JAVA";
        System.out.println("=== 示例4：未匹配 ===");
        System.out.println("indexOf结果: " + indexOf(text4, pattern4));
    }
}

关键代码解读

前缀函数构建中的 while 回退

while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
    k = pi[k - 1];
}

这是KMP最精妙的一行。当当前字符不匹配时，我们不是简单地将 k 归零，而是跳到 pi[k-1] 所指示的位置。因为 pi[k-1] 告诉我们：pattern[0..k-1] 的最长相等真前缀长度，这意味着这部分前缀无需重新比较。

匹配成功后的 k = pi[k-1]

if (k == pattern.length()) {
    matches.add(i - pattern.length() + 1);
    k = pi[k - 1]; // 关键：允许重叠匹配
}

找到一次完整匹配后，将 k 回退到 pi[k-1]，而不是归零。这使得KMP能够高效处理重叠匹配场景（如在AAAAA中找AA）。

复杂度分析

相比暴力解法的 O(m×n)，KMP在最坏情况下（如主串为AAAAAAAAAB，模式串为AAAAB）也能保持线性性能。

扩展：KMP的变体与应用

1. 多模式匹配：结合AC自动机（Aho-Corasick），可同时搜索多个模式串
2. 循环节检测：利用前缀函数可 O(n) 找出字符串的最小循环节
3. 字符串压缩：分析前缀函数数组可发现重复模式，辅助Run-Length编码
4. 数据库索引：某些全文搜索引擎在底层使用KMP或BM（Boyer-Moore）进行子串定位

总结

KMP算法的核心贡献在于 “利用已匹配信息避免重复比较”。通过前缀函数这一预处理结构，它将对主串的扫描优化到严格的一次遍历，是”空间换时间”策略的经典范例。

掌握KMP不仅是应对面试的需要，更能够训练对字符串结构与状态回退的直觉——这种思维在编译原理的词法分析、正则表达式引擎、乃至DNA序列分析中都有深远应用。