每日算法 — 使用java实现KMP字符串匹配：前缀函数与线性时间复杂度

算法背景

字符串匹配是计算机科学中最基础的问题之一：给定一个文本串 text 和一个模式串 pattern，找出 pattern 在 text 中所有出现的位置。暴力解法的时间复杂度为 O(m×n)，而 KMP（Knuth-Morris-Pratt）算法通过构建前缀函数（Prefix Function），将匹配过程优化到 O(m+n) 的线性时间，是字符串算法的经典之作。

核心思想

KMP 的核心在于利用已匹配的信息避免回退。当匹配失败时，模式串不需要从头开始比较，而是根据前缀函数跳转到最长相同前缀后缀的位置继续匹配。

前缀函数 pi[i] 定义为：子串 pattern[0..i] 的最长相等真前缀与真后缀的长度。例如对于模式串 "ababc"，pi 数组为 [0,0,1,2,0]。

完整Java实现

public class KMPMatcher {

    /**
     * 计算前缀函数（π数组）
     * @param pattern 模式串
     * @return 前缀函数数组
     */
    public static int[] computePrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        // pi[0] 恒为0，从i=1开始计算
        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];
            }
            // 如果匹配成功，长度加1
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        return pi;
    }

    /**
     * KMP字符串匹配
     * @param text 文本串
     * @param pattern 模式串
     * @return 所有匹配起始位置的列表
     */
    public static java.util.List<Integer> kmpSearch(String text, String pattern) {
        java.util.List<Integer> result = new java.util.ArrayList<>();
        if (pattern.isEmpty() || text.length() < pattern.length()) {
            return result;
        }

        int[] pi = computePrefixFunction(pattern);
        int j = 0; // pattern中的当前匹配位置

        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()) {
                result.add(i - pattern.length() + 1);
                j = pi[j - 1]; // 继续寻找下一个匹配
            }
        }
        return result;
    }

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

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

        System.out.println("文本串: " + text);
        System.out.println("模式串: " + pattern);

        int[] pi = computePrefixFunction(pattern);
        System.out.print("前缀函数: ");
        for (int v : pi) System.out.print(v + " ");
        System.out.println();

        java.util.List<Integer> matches = kmpSearch(text, pattern);
        System.out.println("匹配位置: " + matches);
        System.out.println("出现次数: " + matches.size());

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

复杂度分析

前缀函数计算：每个位置 i 最多被访问两次（一次作为当前位置，一次被回退），时间复杂度 O(m)，空间复杂度 O(m)。
匹配过程：同理，文本串每个位置最多被访问两次，时间复杂度 O(n)。
总体复杂度：O(m+n) 时间，O(m) 额外空间。

应用场景

KMP算法广泛应用于文本编辑器查找、DNA序列比对、网络数据包过滤、日志分析等需要高效字符串匹配的场景。理解KMP的前缀函数思想，也是掌握AC自动机、Z函数等高级字符串算法的基础。

Tagged with: KMP 前缀函数字符串匹配