KMP 算法详解：字符串匹配的高效之道

创作时间:

作者:

@小白创作中心

KMP 算法详解：字符串匹配的高效之道

引用

CSDN

https://blog.csdn.net/2301_78858041/article/details/146207728

在编程世界中，字符串匹配是一个非常常见的需求。无论是搜索引擎、文本编辑器，还是病毒扫描软件，都需要快速定位目标字符串。传统的暴力匹配算法虽然简单，但在最坏情况下时间复杂度高达 O(n*m)，其中 n 是主串长度，m 是模式串长度。这在处理大规模数据时显然不够高效。而 KMP 算法（Knuth-Morris-Pratt Algorithm）则是字符串匹配领域的“性能之王”。它通过预处理模式串，将时间复杂度降低到 O(n + m)，堪称字符串匹配的最优解！

KMP 算法的核心原理

字符串匹配的困境

假设我们要在一个长文本中搜索某个关键词。暴力匹配算法的工作方式是逐个字符比较主串和模式串：

public static boolean bruteForce(String text, String pattern) {
    int n = text.length(); 
    int m = pattern.length(); 
    for (int i = 0; i <= n - m; i++) {
        for (int j = 0; j < m; j++) {
            if (text.charAt(i  + j) != pattern.charAt(j))  {
                break;
            }
        }
        if (j == m) {
            return true;
        }
    }
    return false;
}

问题：

如果模式串很长，且大部分字符不匹配，暴力匹配会浪费大量时间。
在最坏情况下（如主串全是 A，模式串是 AAAAAC），时间复杂度高达 O(n*m)。

KMP 算法的核心思想

KMP 算法的核心思想是：利用已匹配的部分信息，避免重复比较。具体来说：

预处理模式串：构建一个“前缀函数”（也称为“最长前缀后缀”数组），记录模式串中每个位置的最大匹配前缀长度。
状态转移：在匹配过程中，当出现不匹配时，根据前缀函数快速跳转到下一个可能匹配的位置，而不是重新从头开始匹配。

比喻：
KMP 算法就像一个聪明的侦探，在犯罪现场寻找线索时不会每次都从头开始排查。他会根据之前找到的线索（已匹配的部分），直接跳转到最有可能的位置继续排查。

KMP 算法的实现步骤

计算前缀函数

前缀函数是 KMP 算法的灵魂。它的作用是记录模式串中每个位置的最大匹配前缀长度。

示例：模式串 "ABABX" 的前缀函数
索引 0 1 2 3 4
字符 A B A B X
前缀函数值 0 0 1 2 0

计算前缀函数的步骤：

初始化 prefix[0] = 0。
从第 1 个字符开始遍历模式串。
对于每个字符 pattern[i]，找到最大的 k 使得 pattern[0..k-1] == pattern[i-k+1..i]。

代码实现：

public static int[] computePrefixFunction(String pattern) {
    int m = pattern.length(); 
    int[] prefix = new int[m];
    prefix[0] = 0;
    for (int i = 1; i < m; i++) {
        int k = prefix[i - 1];
        while (k > 0 && pattern.charAt(i)  != pattern.charAt(k))  {
            k = prefix[k - 1];
        }
        if (pattern.charAt(i)  == pattern.charAt(k))  {
            k++;
        }
        prefix[i] = k;
    }
    return prefix;
}

深入理解：

前缀函数的作用是记录模式串中每个位置的最大匹配前缀长度。
这个数组将指导我们在匹配失败时如何跳转到下一个可能的位置。

KMP 匹配算法

有了前缀函数后，我们就可以进行高效的字符串匹配了。

代码实现：

public static boolean kmpSearch(String text, String pattern) {
    int n = text.length(); 
    int m = pattern.length(); 
    if (m == 0) {
        return true;
    }
    int[] prefix = computePrefixFunction(pattern);
    int q = 0;
    for (int i = 0; i < n; i++) {
        while (q > 0 && text.charAt(i)  != pattern.charAt(q))  {
            q = prefix[q - 1];
        }
        if (text.charAt(i)  == pattern.charAt(q))  {
            q++;
        }
        if (q == m) {
            return true;
        }
    }
    return false;
}

步骤解释：