介绍
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，核心思想是利用已经部分匹配的信息，避免重复比较，在文本串中快速查找模式串。KMP算法特别适合处理长文本和重复性高的模式串，时间复杂度是O(m+n)，m是模式串长度，n是文本串长度。
KMP算法的关键在于构建一个部分匹配表（也叫失败函数或者next数组），这个表记录了当匹配失败时，模式串指针应该回退到的位置，让算法跳过已知不可能匹配的位置，提高匹配效率。
算法步骤
KMP算法主要分为两个阶段：
预处理阶段：计算模式串的部分匹配表（next数组）
构建一个数组，记录每个位置的最长相等前后缀长度
该数组用于在匹配失败时确定模式串指针的回退位置
匹配阶段：使用部分匹配表在文本串中查找模式串
从左到右同时遍历文本串和模式串
当字符不匹配时，根据next数组回退模式串指针
当模式串完全匹配时，记录匹配位置并继续查找其他匹配
核心特性
线性时间复杂度：O(m+n)，其中m是模式串长度，n是文本串长度
高效利用历史信息：通过预处理避免了重复比较
只需一次遍历文本串：文本串指针不会回退
空间复杂度：O(m)，仅需存储模式串的部分匹配表
适用场景：特别适合长文本和具有重复性的模式串
基础实现
暴力解法
先看下暴力解法：
public class NaiveStringMatcher {
/**
* 朴素字符串匹配算法
* @param text 文本串
* @param pattern 模式串
* @return 匹配成功则返回模式串在文本串中的起始位置，否则返回-1
*/
public static int naiveSearch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
// 特殊情况处理
if (m == 0) return 0;
if (n < m) return -1;
// 尝试所有可能的匹配位置
for (int i = 0; i <= n - m; i++) {
int j;
// 从当前位置开始比较模式串和文本串
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
break; // 发现不匹配字符，终止内层循环
}
}
// 如果j等于m，说明模式串完全匹配
if (j == m) {
return i; // 返回匹配位置
}
}
return -1; // 未找到匹配
}
// 使用示例
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int position = naiveSearch(text, pattern);
if (position == -1) {
System.out.println("未找到匹配");
} else {
System.out.println("模式串在位置 " + position + " 处匹配");
}
}
}
上述实现暴力枚举所有可能的匹配位置，逐一比较文本串与模式串的每个字符，直到找到完全匹配或确定不存在匹配。
接下来展示KMP算法的实现：
Java实现
public class KMP {
// 构建部分匹配表（next数组）
private static int[] buildNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
next[0] = 0; // 第一个字符的最长相等前后缀长度为0
for (int i = 1, j = 0; i < m; i++) {
// 当前字符不匹配，回退j
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
// 当前字符匹配，j向前移动
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
// 记录当前位置的最长相等前后缀长度
next[i] = j;
}
return next;
}
// KMP搜索算法
public static int kmpSearch(String text, String pattern) {
if (pattern == null || pattern.length() == 0) {
return 0;
}
if (text == null || text.length() < pattern.length()) {
return -1;
}
int n = text.length();
int m = pattern.length();
// 构建next数组
int[] next = buildNext(pattern);
// 进行匹配
for (int i = 0, j = 0; i < n; i++) {
// 当前字符不匹配，根据next数组回退j
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
// 当前字符匹配，j向前移动
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
// 完全匹配，返回起始索引
if (j == m) {
return i - m + 1;
}
}
return -1; // 未找到匹配
}
// 查找所有匹配位置
public static List<Integer> kmpSearchAll(String text, String pattern) {
List<Integer> positions = new ArrayList<>();
if (pattern == null || pattern.length() == 0) {
return positions;
}
if (text == null || text.length() < pattern.length()) {
return positions;
}
int n = text.length();
int m = pattern.length();
// 构建next数组
int[] next = buildNext(pattern);
// 进行匹配
for (int i = 0, j = 0; i < n; i++) {
// 当前字符不匹配，回退j
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
// 当前字符匹配，j向前移动
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
// 完全匹配，记录位置并继续匹配
if (j == m) {
positions.add(i - m + 1);
// 回退j以寻找下一个匹配
j = next[j - 1];
}
}
return positions;
}
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int pos = kmpSearch(text, pattern);
List<Integer> allPos = kmpSearchAll(text, pattern);
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
System.out.println("首次匹配位置: " + (pos != -1 ? pos : "未找到"));
System.out.println("所有匹配位置: " + allPos);
// 打印next数组，帮助理解
int[] next = buildNext(pattern);
System.out.print("next数组: ");
for (int val : next) {
System.out.print(val + " ");
}
System.out.println();
}
}
在上述代码中，
// 当前字符不匹配，回退j
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
是 KMP 算法的核心，在匹配失败时根据预先计算的next数组来确定模式串指针的回退位置。
Python实现
def build_next(pattern):
m = len(pattern)
next_array = [0] * m
for i in range(1, m):
j = next_array[i - 1]
while j > 0 and pattern[i] != pattern[j]:
j = next_array[j - 1]
if pattern[i] == pattern[j]:
j += 1
next_array[i] = j
return next_array
def kmp_search(text, pattern):
if not pattern:
return 0
if not text or len(text) < len(pattern):
return -1
n, m = len(text), len(pattern)
next_array = build_next(pattern)
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = next_array[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
return i - m + 1
return -1
# 测试
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(f"文本: {text}")
print(f"模式: {pattern}")
print(f"匹配位置: {kmp_search(text, pattern)}")
print(f"next数组: {build_next(pattern)}")
优化策略
优化后的 next 数组代码实现：
// 优化next数组，避免匹配失败后回退到同样会失败的位置
private static int[] buildOptimizedNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
next[0] = 0;
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
// 当前位置匹配失败时，如果回退位置的字符与当前位置相同，则继续回退
if (i + 1 < m && pattern.charAt(i + 1) == pattern.charAt(j)) {
next[i] = next[j - 1];
} else {
next[i] = j;
}
}
return next;
}
预处理减少分支实现：
// 预处理字符映射，减少字符比较的分支
public static int kmpSearchOptimized(String text, String pattern) {
if (pattern == null || pattern.length() == 0) {
return 0;
}
if (text == null || text.length() < pattern.length()) {
return -1;
}
int n = text.length();
int m = pattern.length();
// 使用数组映射来加速字符比较（假设字符集为ASCII）
// 为每个模式字符的每个位置创建一个状态转移表
int[][] dfa = new int[256][m];
// 初始化第一个字符的DFA
dfa[pattern.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < m; j++) {
// 复制匹配失败情况下的值
for (int c = 0; c < 256; c++) {
dfa[c][j] = dfa[c][X];
}
// 设置匹配成功情况下的值
dfa[pattern.charAt(j)][j] = j + 1;
// 更新重启状态
X = dfa[pattern.charAt(j)][X];
}
// 模式匹配
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
j = dfa[text.charAt(i)][j];
}
if (j == m) {
return i - m; // 找到匹配
} else {
return -1; // 未找到匹配
}
}
优缺点
优点
时间复杂度为O(m+n)，优于朴素的字符串匹配算法(暴力解法)
文本串只需扫描一次，不会回退
对于包含重复模式的字符串会高效
预处理模式串，可以多次用于不同的文本串
能快速跳过已知不会匹配的位置
缺点
需要额外的空间存储next数组
构建next数组的逻辑较为复杂，不易理解
在模式串较短或无重复模式时，相比简单算法优势不明显
实现时容易出错，特别是处理边界情况
应用场景
1）生物信息学中的DNA序列匹配
2）网络入侵检测系统中的模式匹配
3）搜索引擎的关键词匹配
4）数据压缩算法中的模式识别
扩展
多模式字符串匹配
// Aho-Corasick算法 - KMP的多模式扩展
public static class AhoCorasick {
static class TrieNode {
TrieNode[] children = new TrieNode[256];
TrieNode fail;
List<Integer> patternIndices = new ArrayList<>();
public TrieNode() {
fail = null;
}
}
private TrieNode root;
private String[] patterns;
public AhoCorasick(String[] patterns) {
this.patterns = patterns;
buildTrie();
buildFailureLinks();
}
private void buildTrie() {
root = new TrieNode();
for (int i = 0; i < patterns.length; i++) {
String pattern = patterns[i];
TrieNode node = root;
for (char c : pattern.toCharArray()) {
if (node.children[c] == null) {
node.children[c] = new TrieNode();
}
node = node.children[c];
}
node.patternIndices.add(i);
}
}
private void buildFailureLinks() {
Queue<TrieNode> queue = new LinkedList<>();
// 初始化根节点的子节点
for (int i = 0; i < 256; i++) {
if (root.children[i] != null) {
root.children[i].fail = root;
queue.offer(root.children[i]);
} else {
root.children[i] = root;
}
}
// BFS构建失败链接
while (!queue.isEmpty()) {
TrieNode node = queue.poll();
for (int i = 0; i < 256; i++) {
if (node.children[i] != null) {
TrieNode failNode = node.fail;
while (failNode != root && failNode.children[i] == null) {
failNode = failNode.fail;
}
failNode = failNode.children[i];
node.children[i].fail = failNode;
// 合并匹配结果
node.children[i].patternIndices.addAll(failNode.patternIndices);
queue.offer(node.children[i]);
}
}
}
}
public List<Pair<Integer, Integer>> search(String text) {
List<Pair<Integer, Integer>> results = new ArrayList<>();
TrieNode currentState = root;
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
while (currentState != root && currentState.children[c] == null) {
currentState = currentState.fail;
}
currentState = currentState.children[c];
for (int patternIndex : currentState.patternIndices) {
int endPos = i;
int startPos = endPos - patterns[patternIndex].length() + 1;
results.add(new Pair<>(patternIndex, startPos));
}
}
return results;
}
static class Pair<K, V> {
K first;
V second;
public Pair(K first, V second) {
this.first = first;
this.second = second;
}
}
}
测验
这里准备了一些测试题，方便大家判断自己的掌握情况：
KMP算法的时间复杂度是多少？它与暴力匹配算法的主要区别是什么？
KMP算法中next数组的含义是什么？如何利用它避免不必要的比较？
在KMP算法中，文本指针是否会回退？为什么？
测验答案
KMP算法的时间复杂度是O(m+n)，其中m是模式串长度，n是文本串长度。与暴力匹配算法O(m*n)相比，KMP算法利用已匹配信息避免重复比较，文本指针不会回退。
next数组记录了模式串中每个位置的最长相等前后缀长度，表示当匹配失败时，模式串指针应该回退到的位置。通过跳过已知不可能匹配的位置，实现减少不必要的比较次数。
文本指针不会回退，只有模式串指针会根据next数组回退。因为KMP算法的核心思想就是利用已经部分匹配的信息，避免对文本串的重复扫描。
相关的 LeetCode 热门题目
给大家推荐一些可以用来练手的 LeetCode 题目：
28. 找出字符串中第一个匹配项的下标 - 标准的字符串匹配问题
214. 最短回文串 - 可以使用KMP算法的next数组思想解决
459. 重复的子字符串 - 使用KMP的next数组判断字符串是否由重复子串构成
KMP算法是字符串处理中的经典算法，用来解决字符串匹配问题，理解它对提升算法设计能力还是很有帮助的
