KMP算法（字符串匹配最优经典算法）

KMP算法是字符串匹配领域的最优经典高效算法。KMP算法是对「BF暴力匹配算法」的极致优化，彻底解决了BF算法大量无效回退、重复比较的核心缺陷

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、KMP算法的核心概念

前置约定

• 主串：记为 S，长度 $n$，下标 $0\sim n-1$
• 模式串：记为 T，长度 $m$，下标 $0\sim m-1$
• 核心指针：i（主串指针，只前进不后退）、j（模式串指针，按需回退）

1. 最长相等前后缀

这是KMP算法的灵魂核心，所有逻辑都围绕这个概念展开，必须彻底理解！

定义

对于模式串的子串 T[0...j]（从模式串开头到当前下标j的子串），找到一个最长的长度k，满足：

这个子串的前缀 和 后缀 完全相等，且 $k<j+1$（不能是子串本身）

✅ 前缀：字符串必须从第一个字符开始，不包含最后一个字符的连续子串；
✅ 后缀：字符串必须到最后一个字符结束，不包含第一个字符的连续子串；

举例理解

• 案例1：模式串子串 T = "ababc"，求下标4(字符c)对应的最长相等前后缀
  子串是"ababc"，所有前缀：a,ab,aba,abab；所有后缀：c,bc,abc,babc → 无相等前后缀 → 长度=0
• 案例2：模式串子串 T = "abab"，求下标3对应的最长相等前后缀
  前缀：a,ab,aba；后缀：b,ab,bab → 最长相等的是ab → 长度=2
• 案例3：模式串子串 T = "aaaa"，求下标3对应的最长相等前后缀
  前缀：a,aa,aaa；后缀：a,aa,aaa → 最长相等的是aaa → 长度=3
• 特殊值：模式串第一个字符（j=0），没有前缀和后缀 → 最长相等前后缀长度固定为0

2. 部分匹配表（PMT表）→ 核心数组：next数组

定义

基于「最长相等前后缀」，构建一个和模式串长度相同的数组 next[]，数组的下标对应模式串的下标j，数组的值 next[j] 表示：

模式串子串 T[0...j] 的最长相等前后缀的长度

next数组 是KMP算法的核心数据结构，所有匹配的回退逻辑都由它决定，求next数组是KMP的第一核心步骤！

举例：经典模式串求next数组

模式串 T = "ababx"，长度m=5，手动推导完整next数组：

• j=0 → 子串a → 无前后缀 → next[0] = 0
• j=1 → 子串ab → 前缀a，后缀b → 无相等 → next[1] = 0
• j=2 → 子串aba → 前缀a，后缀a → 最长长度=1 → next[2] = 1
• j=3 → 子串abab → 前缀ab，后缀ab → 最长长度=2 → next[3] = 2
• j=4 → 子串ababx → 无相等前后缀 → next[4] = 0

最终next数组：[0,0,1,2,0]

---

二、KMP算法的完整执行流程

KMP算法分为两个核心步骤，顺序不可逆，缺一不可，所有代码实现都遵循这个流程：

✅ 步骤1：预处理模式串，求模式串的 next数组

✅ 步骤2：利用next数组，执行主串和模式串的高效匹配（主串指针永不回退）

---

三、步骤1：求next数组

1. next数组的求解逻辑（双指针法，时间复杂度$O(m)$）

初始化两个指针，专门用于求模式串的最长相等前后缀：

• 指针 j：初始值0，代表「前缀的末尾下标」，也代表当前最长相等前后缀的长度
• 指针 i：初始值1，代表「后缀的末尾下标」，遍历整个模式串（从1开始）

核心规则（循环执行，直到i遍历完模式串）

模式串记为 T，数组记为 next[]，next[0] = 0 是固定值：

1. 若 T[i] == T[j]：前后缀匹配成功 → j++，next[i] = j，i++；
2. 若 T[i] != T[j]：前后缀匹配失败 → j根据next数组回退：j = next[j-1]，直到j=0为止；
   • 若回退后j=0且T[i] != T[j] → next[i] = 0，i++；

2. next数组求解 代码实现（Java）

/**
 * 求模式串的next数组（核心预处理方法）
 * @param pattern 模式串
 * @return 模式串对应的next数组
 */
private static int[] getNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = 0; // 第一个字符的最长相等前后缀长度固定为0
    int j = 0; // 前缀指针：代表最长相等前后缀的长度，初始0
    int i = 1; // 后缀指针：遍历模式串，初始1
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
            next[i] = j;
            i++;
        } else {
            if (j > 0) {
                // 匹配失败，j回退到上一个最长相等前后缀的位置
                j = next[j - 1];
            } else {
                // j=0，无法回退，当前位置无相等前后缀
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

3. 验证：模式串ababx求next数组

调用上述方法，传入pattern="ababx"，返回的next数组为 [0,0,1,2,0]，和手动推导一致 ✔️

---

四、步骤2：KMP核心匹配流程

这是KMP的最终执行步骤，基于预处理好的next数组，实现主串和模式串的高效匹配，核心优势：主串指针i永不回退

匹配规则（初始化+核心循环+终止条件）

1. 初始化指针：主串指针 i=0，模式串指针 j=0；主串长度n，模式串长度m；
2. 核心匹配循环（i < n 且 j < m）：
   • ✅ 匹配成功：S[i] == T[j] → 双指针同时后移，i++，j++，继续匹配下一个字符；
   • ❌ 匹配失败：S[i] != T[j] →
     • 如果 j > 0：模式串指针根据next数组回退 → j = next[j-1]，主串指针i不变；
     • 如果 j = 0：模式串指针无法回退 → 主串指针后移i++，模式串指针保持j=0；
3. 匹配终止条件：
   • ✅ 匹配成功：当 j == m 时，说明模式串全部匹配完成，返回匹配起始下标 = i - j；
   • ❌ 匹配失败：当 i == n 时，说明主串遍历完毕，始终未匹配完整模式串，返回 -1；

核心优化点对比（KMP vs BF）

• BF算法失败：i = i-j+1（主串回退）、j=0（模式串重置）→ 大量重复比较；
• KMP算法失败：i不变（主串不回退）、j=next[j-1]（模式串智能回退）→ 无重复比较；

---

五、KMP算法完整代码实现

整合「求next数组」+「KMP核心匹配」，附带边界条件处理+多测试案例，是最标准的KMP实现版本：

public class KMPAlgorithm {
    // 求模式串的next数组（预处理核心方法）
    private static int[] getNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0;
        int j = 0;
        int i = 1;
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
                next[i] = j;
                i++;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    next[i] = 0;
                    i++;
                }
            }
        }
        return next;
    }

    /**
     * KMP核心匹配方法
     * @param mainStr 主串（被查找的长字符串）
     * @param patternStr 模式串（要查找的短字符串）
     * @return 匹配成功返回起始下标；匹配失败返回-1；边界情况做健壮性处理
     */
    public static int kmpMatch(String mainStr, String patternStr) {
        // 边界条件处理
        if (mainStr == null || patternStr == null) return -1;
        int n = mainStr.length();
        int m = patternStr.length();
        if (m == 0) return 0;
        if (n < m) return -1;

        int[] next = getNext(patternStr); // 步骤1：预处理得到next数组
        int i = 0; // 主串指针，永不回退
        int j = 0; // 模式串指针，按需回退

        // 步骤2：核心匹配循环
        while (i < n && j < m) {
            if (mainStr.charAt(i) == patternStr.charAt(j)) {
                i++;
                j++;
            } else {
                if (j > 0) {
                    j = next[j - 1]; // 模式串智能回退
                } else {
                    i++; // j=0，主串指针后移
                }
            }
        }

        // 判断匹配结果
        if (j == m) {
            return i - j; // 返回匹配起始下标
        } else {
            return -1; // 匹配失败
        }
    }

    // 测试主方法：多案例验证KMP正确性
    public static void main(String[] args) {
        // 案例1：经典测试
        String s1 = "abcabx";
        String t1 = "abx";
        System.out.println("案例1匹配下标：" + kmpMatch(s1, t1)); // 输出：3 ✔️

        // 案例2：BF算法最坏情况，KMP优势最大化
        String s2 = "aaaaaab";
        String t2 = "aaab";
        System.out.println("案例2匹配下标：" + kmpMatch(s2, t2)); // 输出：3 ✔️

        // 案例3：无匹配结果
        String s3 = "abcdefg";
        String t3 = "xyz";
        System.out.println("案例3匹配下标：" + kmpMatch(s3, t3)); // 输出：-1 ✔️

        // 案例4：完全匹配
        String s4 = "hello kmp world";
        String t4 = "kmp";
        System.out.println("案例4匹配下标：" + kmpMatch(s4, t4)); // 输出：6 ✔️
    }
}

代码运行结果

案例1匹配下标：3
案例2匹配下标：3
案例3匹配下标：-1
案例4匹配下标：6

---

六、KMP算法的时间复杂度 & 空间复杂度

✅ 时间复杂度

KMP算法的时间复杂度分为两部分，且无最好/最坏之分，恒定最优：

1. 预处理求next数组：只遍历模式串一次 → $O(m)$；
2. 核心匹配过程：主串指针i只前进不后退，最多遍历n次；模式串指针j只会回退，总回退次数不超过前进次数 → $O(n)$；

整体时间复杂度：$\mathbf{O}(\mathbf{n}+\mathbf{m})$

✅ 对比BF算法的最坏$O(n\times m)$，KMP的优化是质的飞跃！尤其是在长字符串匹配场景下，效率差距天壤之别。

✅ 空间复杂度

$O(m)$

• 解释：KMP算法需要额外开辟一个长度为m的next数组，存储模式串的最长相等前后缀信息，空间开销由模式串长度决定；
• 补充：BF算法空间复杂度是$O(1)$，这是BF唯一优于KMP的点。

---

七、核心知识点速记

1. KMP是BF的优化版，解决BF「无效回退、重复比较」的缺陷，核心：主串指针i永不回退；
2. KMP的灵魂是「最长相等前后缀」，前缀必须从头开始，后缀必须从尾结束，不能是子串本身；
3. next数组的每个值next[j]，就是模式串T[0..j]的最长相等前后缀长度，next[0]=0是固定值；
4. KMP两步走：①求模式串的next数组 ②用next数组做高效匹配；
5. 匹配失败时，模式串指针回退规则：j = next[j-1]（j>0时）；
6. KMP时间复杂度恒定$O(n+m)$，空间复杂度$O(m)$，是字符串匹配的最优经典算法；