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

创作时间:

作者:

@小白创作中心

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

引用

CSDN

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

KMP算法是字符串匹配领域的经典算法之一，通过预处理模式串，利用已匹配的信息快速跳转，从而实现了高效的匹配过程。本文将从零开始，逐步揭开KMP算法的神秘面纱，并结合源码和实际案例，帮助你彻底理解它的原理和实现！

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

步骤解释：