每日算法 — 使用java实现KMP算法：前缀函数与线性模式匹配

字符串模式匹配是计算机科学中最基础也最重要的问题之一。从文本编辑器的查找功能到搜索引擎的关键词检索，从DNA序列比对到网络入侵检测，模式匹配无处不在。KMP算法（Knuth-Morris-Pratt）通过巧妙利用已匹配信息，将时间复杂度从暴力算法的O(m×n)优化到O(m+n)，是字符串算法的里程碑。本文将深入讲解前缀函数的构建原理，并用Java实现完整的KMP算法。

暴力匹配的问题

朴素的字符串匹配算法逐个字符比较，一旦不匹配就回溯到模式的下一个起始位置。最坏情况下需要O(m×n)次比较。

文本:    a b a b a b c a b c a b
模式:    a b a b a b c a b
匹配到第9个字符时发现不匹配，暴力算法会回溯到文本第2个字符重新开始。

KMP算法的核心洞察是：已匹配的部分本身就包含了模式的信息，可以利用这些信息决定下一次比较的位置，避免不必要的回溯。

前缀函数（Prefix Function / LPS数组）

前缀函数π[i]定义为：模式串p[0..i]的最长相等真前缀和真后缀的长度。

真前缀：不等于自身的所有前缀
真后缀：不等于自身的所有后缀

例如，对于模式串 “ababaca”：

前缀函数的Java实现

/**
 * 计算前缀函数（LPS - Longest Prefix Suffix）
 * 时间复杂度: O(m)，其中m为模式串长度
 */
public static int[] computePrefixFunction(String pattern) {
    int m = pattern.length();
    int[] pi = new int[m];

    // pi[0] 恒为 0
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1]; // j表示前一个位置的最长相等前后缀长度

        // 如果当前字符不匹配，回退到更短的前缀
        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;
}

KMP匹配算法

利用前缀函数，当文本与模式在位置i不匹配时，不需要回溯文本指针，只需根据前缀函数将模式向右移动适当距离，继续比较。

完整Java实现

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

/**
 * KMP算法完整实现
 * 时间复杂度: O(m + n)
 * 空间复杂度: O(m)
 */
public class KMPAlgorithm {

    /**
     * 计算前缀函数（LPS数组）
     */
    public static int[] computePrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];

        for (int i = 1; i < m; i++) {
            int j = pi[i - 1];

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

    /**
     * KMP字符串匹配
     * @param text 文本串
     * @param pattern 模式串
     * @return 所有匹配起始位置的列表
     */
    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 = computePrefixFunction(pattern);
        int j = 0; // 模式串中的当前匹配位置

        for (int i = 0; i < text.length(); i++) {
            // 当不匹配时，根据前缀函数回退
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }

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

            // 完全匹配模式串
            if (j == pattern.length()) {
                matches.add(i - pattern.length() + 1); // 记录起始位置
                j = pi[j - 1]; // 继续搜索（允许重叠匹配）
            }
        }

        return matches;
    }

    /**
     * KMP匹配过程可视化（调试用）
     */
    public static void visualizeMatch(String text, String pattern) {
        int[] pi = computePrefixFunction(pattern);

        System.out.println("模式串: " + pattern);
        System.out.print("LPS数组: ");
        for (int v : pi) {
            System.out.print(v + " ");
        }
        System.out.println("\n");

        int j = 0;
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                System.out.printf("在text[%d]='%c'与pattern[%d]='%c'不匹配，回退j=%d→%d%n",
                    i, text.charAt(i), j, pattern.charAt(j), j, pi[j - 1]);
                j = pi[j - 1];
            }

            if (text.charAt(i) == pattern.charAt(j)) {
                System.out.printf("text[%d]='%c' == pattern[%d]='%c', j=%d→%d%n",
                    i, text.charAt(i), j, pattern.charAt(j), j, j + 1);
                j++;
            }

            if (j == pattern.length()) {
                System.out.println("*** 找到匹配，起始位置: " + (i - pattern.length() + 1) + " ***");
                j = pi[j - 1];
            }
        }
    }

    /**
     * 统计模式串在文本中的出现次数（允许重叠）
     */
    public static int countOccurrences(String text, String pattern) {
        return kmpSearch(text, pattern).size();
    }

    /**
     * 查找文本中第一个匹配位置
     */
    public static int findFirst(String text, String pattern) {
        List<Integer> matches = kmpSearch(text, pattern);
        return matches.isEmpty() ? -1 : matches.get(0);
    }

    /**
     * 多模式匹配：同时搜索多个模式
     * 对每个模式分别运行KMP
     */
    public static java.util.Map<String, List<Integer>> multiPatternSearch(
            String text, String[] patterns) {
        java.util.Map<String, List<Integer>> results = new java.util.HashMap<>();
        for (String pattern : patterns) {
            results.put(pattern, kmpSearch(text, pattern));
        }
        return results;
    }

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

        System.out.println("=== KMP算法演示 ===");
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern + "\n");

        // 可视化匹配过程
        visualizeMatch(text, pattern);

        System.out.println("\n=== 匹配结果 ===");
        List<Integer> matches = kmpSearch(text, pattern);
        System.out.println("所有匹配位置: " + matches);
        System.out.println("出现次数: " + countOccurrences(text, pattern));

        // 重叠匹配测试
        String text2 = "aaaaa";
        String pattern2 = "aaa";
        System.out.println("\n重叠匹配测试:");
        System.out.println("文本: " + text2 + ", 模式: " + pattern2);
        System.out.println("匹配位置: " + kmpSearch(text2, pattern2));

        // 多模式匹配
        System.out.println("\n多模式匹配:");
        String[] patterns = {"abc", "cab", "bca"};
        var multiResults = multiPatternSearch(text, patterns);
        for (var entry : multiResults.entrySet()) {
            System.out.println("模式 '" + entry.getKey() + "' 匹配位置: " + entry.getValue());
        }
    }
}

前缀函数的回退机制图解

假设模式为 “ababac”，当前已匹配到 “ababab”（i=5）时发现最后一个字符不匹配：

文本: ... a b a b a b ? ...
模式:     a b a b a c
               ↑
           在位置5不匹配

由于pi[4]=3（”ababa”的最长相等前后缀是”aba”），我们知道模式的前3个字符”aba”已经对齐了文本的末尾，可以直接从位置3继续比较，而不需要移动文本指针。

文本: ... a b a b a b ? ...
模式:         a b a b a c
                   ↑
               从位置3继续

这就是KMP避免回溯的核心机制。

与Z函数和自动机的联系

KMP的前缀函数与Z算法（Z-function）有密切联系。前缀函数可以从Z函数在O(n)时间内推导出来，反之亦然。两者都用于线性时间字符串处理。

从自动机的角度理解，KMP实际上构建了一个前缀自动机（Prefix Automaton），状态表示当前已匹配的前缀长度，转移函数由前缀函数定义。

实际应用场景

1. 文本编辑器：查找/替换功能
2. 搜索引擎：关键词在文档中的定位
3. 生物信息学：DNA序列中查找特定基因片段
4. 网络安全：入侵检测系统中的特征码匹配
5. 数据压缩：LZ77系列算法中的字符串匹配
6. 编译器：词法分析中的关键字识别

复杂度分析

其中σ表示字母表大小。KMP的优势在于保证线性时间且实现简洁，Boyer-Moore在英文文本上通常更快。

扩展：KMP的进阶应用

1. 循环节检测：利用前缀函数求字符串的最小循环节长度
2. 字符串幂运算：判断字符串是否为某个子串的幂次
3. 前缀函数树：将所有前缀函数值连边形成树结构，用于复杂字符串查询
4. 自动机构建：基于前缀函数构建确定性有限自动机（DFA）进行多文本匹配

常见错误

1. 前缀函数下标越界：注意pi[j-1]在j=0时不合法，while条件已保证j>0
2. 匹配后回退位置：完全匹配后应回退到pi[m-1]而非0，以支持重叠匹配
3. 空串处理：空模式应匹配所有位置（包括末尾空位置）
4. 字符编码：处理Unicode时需考虑代理对（surrogate pairs）

总结

KMP算法是字符串处理领域的基石。它展示了如何通过预处理和状态转移来消除回溯，将看似需要O(m×n)的问题优化到O(m+n)。前缀函数的构建过程本身就是一个精妙的动态规划——用前面计算出的信息高效推导后面的值。掌握KMP不仅是学会一个算法，更是理解”利用已知信息避免重复计算”这一核心思想，这种思想在计算机科学的各个领域都有广泛应用。