算法学习笔记：4.KMP 算法——从原理到实战，涵盖 LeetCode 与考研 408 例题

在计算机科学领域，字符串匹配是一项基础且重要的任务，KMP 算法（Knuth-Morris-Pratt 算法）作为字符串匹配算法中的经典之作，以其高效性和巧妙的设计备受关注。无论是在实际编程中处理文本搜索，还是在考研计算机专业基础综合（408）的备考中，掌握 KMP 算法都至关重要。本文将深入剖析 KMP 算法的思路，结合 LeetCode 例题、考研 408 例题进行实战演练，并给出对应解题代码。

一、KMP 算法核心思路

KMP 算法的核心在于利用已经匹配的部分信息，避免不必要的重复比较，从而提高字符串匹配的效率。其关键在于构建部分匹配表（Partial Match Table，也称为最长前缀后缀表），该表记录了模式串每个前缀的最长相等前缀和后缀的长度。

1.1 部分匹配表的构建

假设我们有模式串P = "ABABAC"，构建部分匹配表的过程如下：

1. 初始化：部分匹配表next数组长度与模式串长度相同，next[0] = -1，这是为了后续计算方便，将其看作是一个特殊的边界条件。

1. 遍历模式串：从模式串的第二个字符（索引为 1）开始遍历，设当前遍历到的字符索引为j，用于比较的指针为i = next[j - 1]。

• • 如果P[j] == P[i + 1]，则next[j] = i + 1，表示找到了一个更长的相等前缀和后缀。

• • 否则，不断回溯i = next[i]，直到找到相等的字符或者i回溯到-1，如果还是不相等，则next[j] = -1。

通过上述过程，我们可以得到模式串"ABABAC"的部分匹配表next为[-1, 0, 1, 2, 3, -1]。以下是使用 mermaid 绘制的部分匹配表构建过程示意图：

1.2 字符串匹配过程

有了部分匹配表后，进行字符串匹配时，设主串为T，模式串为P，两个指针i和j分别指向主串和模式串。

1. 初始化：i = 0，j = 0。

1. 比较字符：当T[i] == P[j]时，i和j同时向后移动一位。

1. 失配情况：当T[i] != P[j]时，j = next[j]，即模式串根据部分匹配表进行回溯，而主串的指针i不回溯，继续进行比较。

1. 匹配成功：当j移动到模式串末尾（j == len(P) - 1）时，表示匹配成功；若i移动到主串末尾（i == len(T) - 1）且未匹配成功，则表示模式串在主串中不存在。

二、LeetCode 例题实战

例题 1：28. 找出字符串中第一个匹配项的下标

给定两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"

输出：0

解释："sad" 在下标 0 处匹配。

解题思路：使用 KMP 算法，先构建needle的部分匹配表，然后进行字符串匹配。当匹配成功时，返回主串中匹配的起始下标；若遍历完主串都未匹配成功，则返回-1。

public class StrStr {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        int[] next = buildNext(needle);
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == needle.length()) {
            return i - j;
        }
        return -1;
    }

    private int[] buildNext(String pattern) {
        int length = pattern.length();
        int[] next = new int[length];
        next[0] = -1;
        int i = -1, j = 0;
        while (j < length - 1) {
            if (i == -1 || pattern.charAt(i + 1) == pattern.charAt(j + 1)) {
                i++;
                j++;
                next[j] = i;
            } else {
                i = next[i];
            }
        }
        return next;
    }
}

例题 2：459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1：

输入: s = "abab"

输出: true

解释: 可由子串 "ab" 重复两次构成。

解题思路：将字符串s拼接成s + s，去掉首尾字符后，若s在其中出现，则说明s可以由其子串重复构成。在判断s是否在新字符串中出现时，使用 KMP 算法进行字符串匹配。

public class RepeatedSubstringPattern {
    public boolean repeatedSubstringPattern(String s) {
        String newS = (s + s).substring(1, s.length() * 2 - 1);
        return newS.contains(s);
    }

    // 手动实现KMP算法判断
    public boolean repeatedSubstringPatternKMP(String s) {
        int[] next = buildNext(s);
        int len = s.length();
        if (len % (len - next[len - 1] - 1) == 0 && next[len - 1] != -1) {
            return true;
        }
        return false;
    }

    private int[] buildNext(String pattern) {
        int length = pattern.length();
        int[] next = new int[length];
        next[0] = -1;
        int i = -1, j = 0;
        while (j < length - 1) {
            if (i == -1 || pattern.charAt(i + 1) == pattern.charAt(j + 1)) {
                i++;
                j++;
                next[j] = i;
            } else {
                i = next[i];
            }
        }
        return next;
    }
}

三、考研 408 例题分析

例题：给定主串S = "BBC ABCDAB ABCDABCDABDE"，模式串P = "ABCDABD"，使用 KMP 算法进行字符串匹配，求匹配成功时主串的匹配起始位置。

解题思路：

1. 首先构建模式串P的部分匹配表。

1. 然后按照 KMP 算法的匹配过程，从主串和模式串的开头开始比较。

1. 当出现失配时，根据部分匹配表对模式串进行回溯，继续比较。

1. 直到匹配成功，记录主串的匹配起始位置。

模式串P = "ABCDABD"的部分匹配表next为[-1, 0, 0, 0, 0, 1, 2]。匹配过程如下：

以下是对应的Java 代码实现：

public class KMPMatch {
    public static int kmpMatch(String S, String P) {
        int[] next = buildNext(P);
        int i = 0, j = 0;
        while (i < S.length() && j < P.length()) {
            if (j == -1 || S.charAt(i) == P.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == P.length()) {
            return i - j;
        }
        return -1;
    }

    private static int[] buildNext(String pattern) {
        int length = pattern.length();
        int[] next = new int[length];
        next[0] = -1;
        int i = -1, j = 0;
        while (j < length - 1) {
            if (i == -1 || pattern.charAt(i + 1) == pattern.charAt(j + 1)) {
                i++;
                j++;
                next[j] = i;
            } else {
                i = next[i];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String S = "BBC ABCDAB ABCDABCDABDE";
        String P = "ABCDABD";
        System.out.println(kmpMatch(S, P));
    }
}

四、总结

KMP 算法通过构建部分匹配表，有效减少了字符串匹配过程中的重复比较，大大提高了匹配效率。无论是在 LeetCode 的算法题目中，还是考研 408 的备考过程中，掌握 KMP 算法的思路和应用都能帮助我们更好地解决字符串匹配相关问题。通过本文的详细讲解、例题分析和代码实现，希望读者能对 KMP 算法有更深入的理解和掌握。在实际应用中，还可以根据具体需求对 KMP 算法进行优化和扩展，以适应不同场景下的字符串处理任务。

希望本文能够帮助读者更深入地理解KMP 算法，并在实际项目中发挥其优势。谢谢阅读！

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。