算法学习笔记：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]。匹配过程如下：

步骤	主串 S	模式串 P	比较情况	操作
1	BBC ABCDAB ABCDABCDABDE	ABCDABD	B != A	P 回溯，j = next [0] = -1
2	BBC ABCDAB ABCDABCDABDE	ABCDABD	B != A	P 回溯，j 仍为 -1，i 后移
3	BBC ABCDAB ABCDABCDABDE	ABCDABD	B != A	同步骤 2
4	BBC ABCDAB ABCDABCDABDE	ABCDABD	A == A	i, j 后移
5	BBC ABCDAB ABCDABCDABDE	ABCDABD	B == B	i, j 后移
6	BBC ABCDAB ABCDABCDABDE	ABCDABD	C == C	i, j 后移
7	BBC ABCDAB ABCDABCDABDE	ABCDABD	D == D	i, j 后移
8	BBC ABCDAB ABCDABCDABDE	ABCDABD	A != A	P 回溯，j = next [4] = 0
9	BBC ABCDAB ABCDABCDABDE	ABCDABD	A == A	i, j 后移
10	BBC ABCDAB ABCDABCDABDE	ABCDABD	B == B	i, j 后移
11	BBC ABCDAB ABCDABCDABDE	ABCDABD	C == C	i, j 后移
12	BBC ABCDAB ABCDABCDABDE	ABCDABD	D == D	i, j 后移
13	BBC ABCDAB ABCDABCDABDE	ABCDABD	A == A	i, j 后移
14	BBC ABCDAB ABCDABCDABDE	ABCDABD	B == B	i, j 后移
15	BBC ABCDAB ABCDABCDABDE	ABCDABD	D == D	匹配成功，起始位置为 7

以下是对应的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 算法，并在实际项目中发挥其优势。谢谢阅读！

---

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