详细介绍：今日分享 KMP算法
一、KMP算法是什么？
KMP算法，这名字听着就像三个武林高手Knuth、Morris和Pratt联手打造的独门绝技。这算法厉害之处在于，它能让字符串匹配效率飙升，避免了那些无厘头的“回溯主串”的无用功，只靠“回溯模式串”就能轻松搞定匹配任务，时间复杂度直接优化到O(n+m)，这效率，简直就像给主串和模式串装上了加速器！
二、核心概念：前缀函数（Next数组）
1. 前缀与后缀
前缀：模式串中从第一个字符开始，不包含结果一个字符的子串（如“ababa”的前缀：“a”“ab”“aba”“abab”）。
后缀：模式串中从末了一个字符结束，不包含第一个字符的子串（如“ababa”的后缀：“a”“ba”“aba”“baba”）。
2. 前缀函数定义
对模式串 pattern 的每个位置 i ，前缀函数 next[i] 表示： pattern[0..i] 中最长相等前缀与后缀的长度（若不存在则为0）。
三、KMP匹配步骤
1. 预处理：计算模式串的Next数组。
2. 匹配主串：
用 i 遍历主串 S ， j 遍历模式串 P ；
若 S[i] == P[j] ，则 i++ 、 j++ （继续匹配下一个字符）；
若 S[i] != P[j] ：
若 j > 0 ，则 j = next[j-1] （回溯模式串到最长相等前缀的位置）；
若 j = 0 ，则 i++ （主串后移，模式串从头开始）；
当 j == m （模式串遍历完），说明匹配成功，返回 i - m （匹配起始索引）。
四、例题实战
题目
给定主串 S = "ABABABAAC" ，模式串 P = "ABABC" ，用KMP算法判断模式串是否在主串中出现，若出现则返回第一个匹配的起始索引，否则返回-1。
五、多语言实现
1. C语言实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 计算Next数组
void getNext(char* pattern, int* next, int m) {
int j = 0;
next[0] = 0; // 第一个字符的前缀函数为0
for (int i = 1; i < m; i++) {
// 回溯j到最长相等前缀的位置
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
}
// KMP匹配
int kmpSearch(char* s, char* p) {
int n = strlen(s);
int m = strlen(p);
if (m == 0) return 0;
// 申请Next数组空间
int* next = (int*)malloc(sizeof(int) * m);
getNext(p, next, m);
int j = 0; // 模式串指针
for (int i = 0; i < n; i++) {
// 不匹配时回溯模式串
while (j > 0 && s[i] != p[j]) {
j = next[j - 1];
}
if (s[i] == p[j]) {
j++;
}
// 模式串遍历完，匹配成功
if (j == m) {
free(next);
return i - m + 1;
}
}
free(next);
return -1; // 匹配失败
}
int main() {
char s[] = "ABABABAAC";
char p[] = "ABABC";
int res = kmpSearch(s, p);
if (res != -1) {
printf("模式串在主串中出现，起始索引：%d\n", res);
} else {
printf("模式串未在主串中出现\n");
}
return 0;
}
// 输出：模式串未在主串中出现
2. C++达成
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 计算Next数组
vector<int> getNext(const string& pattern) {
int m = pattern.size();
vector<int> next(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
// KMP匹配
int kmpSearch(const string& s, const string& p) {
int n = s.size();
int m = p.size();
if (m == 0) return 0;
vector<int> next = getNext(p);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && s[i] != p[j]) {
j = next[j - 1];
}
if (s[i] == p[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
int main() {
string s = "ABABABAAC";
string p = "ABABC";
int res = kmpSearch(s, p);
if (res != -1) {
cout << "模式串在主串中出现，起始索引：" << res << endl;
} else {
cout << "模式串未在主串中出现" << endl;
}
return 0;
}
// 输出：模式串未在主串中出现
3. Python构建
def get_next(pattern):
m = len(pattern)
next_arr = [0] * m # 初始化Next数组
j = 0 # 前缀指针
for i in range(1, m):
# 回溯到最长相等前缀的位置
while j > 0 and pattern[i] != pattern[j]:
j = next_arr[j - 1]
if pattern[i] == pattern[j]:
j += 1
next_arr[i] = j
return next_arr
def kmp_search(s, p):
n, m = len(s), len(p)
if m == 0:
return 0
next_arr = get_next(p)
j = 0 # 模式串指针
for i in range(n):
while j > 0 and s[i] != p[j]:
j = next_arr[j - 1]
if s[i] == p[j]:
j += 1
# 匹配成功，返回起始索引
if j == m:
return i - m + 1
return -1 # 匹配失败
# 测试
s = "ABABABAAC"
p = "ABABC"
res = kmp_search(s, p)
if res != -1:
print(f"模式串在主串中出现，起始索引：{res}")
else:
print("模式串未在主串中出现")
# 输出：模式串未在主串中出现
4. Java完成
public class KMPAlgorithm {
// 计算Next数组
private static int[] getNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
// KMP匹配
public static int kmpSearch(String s, String p) {
int n = s.length();
int m = p.length();
if (m == 0) {
return 0;
}
int[] next = getNext(p);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && s.charAt(i) != p.charAt(j)) {
j = next[j - 1];
}
if (s.charAt(i) == p.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
public static void main(String[] args) {
String s = "ABABABAAC";
String p = "ABABC";
int res = kmpSearch(s, p);
if (res != -1) {
System.out.println("模式串在主串中出现，起始索引：" + res);
} else {
System.out.println("模式串未在主串中出现");
}
}
}
// 输出：模式串未在主串中出现