用C语言描述数据结构之KMP算法知识点详解_kmpm,c

一、引言：字符串匹配的重要性

在计算机科学中，字符串匹配（String Matching） 是一个基础而重要的问题。例如：

• 文本编辑器中的“查找”功能
• 搜索引擎的关键词检索
• 网络入侵检测系统（IDS）的关键字识别
• 生物信息学中的DNA序列比对

传统的暴力匹配方法虽然实现简单，但效率较低，时间复杂度为 O(n * m)（n为主串长度，m为模式串长度），不适用于大规模数据。

于是，Knuth-Morris-Pratt 算法（简称 KMP 算法） 被提出，它能在 O(n + m) 的时间内完成字符串匹配任务，极大提升了效率。

本文将使用 C语言 实现 KMP 算法，并详细讲解其原理与实现细节。

---

二、KMP 算法核心思想

2.1 传统暴力匹配的问题

在暴力匹配中，每当发生不匹配时，主串指针会回退到起始位置后一位，模式串也回到起点重新开始。这种“回溯”操作导致了重复比较，浪费了大量时间。

2.2 KMP 的优化策略

KMP 算法的核心在于：

利用已经匹配的部分信息，避免主串指针的回退。

具体来说，当模式串与主串某处失配时，KMP 利用预先计算好的“最长前后缀”信息，仅移动模式串的位置，而不回退主串的指针。

---

三、前缀函数与部分匹配表（PMT）

3.1 前缀函数定义

对于模式串 pattern，其前缀函数数组 lps[]（Longest Prefix Suffix） 定义如下：

lps[i] 表示子串 pattern[0..i] 中，最长的既是前缀又是后缀的子串长度。

例如：

pattern lps 数组 “ababc” [0,0,1,2,3]

3.2 构建 PMT 表的过程详解

以模式串 \"abab\" 为例：

1. i = 0: 子串 \"a\"，没有真前后缀 → lps[0] = 0
2. i = 1: 子串 \"ab\" → 无相同前后缀 → lps[1] = 0
3. i = 2: 子串 \"aba\" → 最长前后缀是 \"a\" → lps[2] = 1
4. i = 3: 子串 \"abab\" → 最长前后缀是 \"ab\" → lps[3] = 2

最终得到 lps = [0,0,1,2]

3.3 C语言实现构建 lps 数组的函数

#include #include // 计算 lps 数组void computeLPS(char* pattern, int* lps) { int len = 0; // 当前最长前缀后缀长度 int i = 1; int m = strlen(pattern); while (i < m) { if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++; } else { if (len != 0) len = lps[len - 1]; // 回退 else { lps[i] = 0; i++; } } }}

---

四、KMP 匹配算法实现（C语言）

4.1 函数原型说明

void kmpSearch(char* text, char* pattern);

• text：主串
• pattern：模式串

4.2 完整代码实现

#include #include // 计算 lps 数组void computeLPS(char* pattern, int* lps) { int len = 0; // 当前最长前缀后缀长度 int i = 1; int m = strlen(pattern); while (i < m) { if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++; } else { if (len != 0) len = lps[len - 1]; // 回退 else { lps[i] = 0; i++; } } }}// KMP 主算法void kmpSearch(char* text, char* pattern) { int n = strlen(text); int m = strlen(pattern); if (m == 0) return; int* lps = (int*)malloc(m * sizeof(int)); computeLPS(pattern, lps); int i = 0; // 主串索引 int j = 0; // 模式串索引 while (i < n) { if (text[i] == pattern[j]) { i++; j++; } if (j == m) { printf(\"匹配成功，起始位置：%d\\n\", i - j); j = lps[j - 1]; // 继续搜索可能的重叠匹配 } else if (i < n && text[i] != pattern[j]) { if (j != 0) j = lps[j - 1]; else i++; } } free(lps);}

4.3 测试程序

int main() { char text[] = \"ababacaabab\"; char pattern[] = \"abab\"; kmpSearch(text, pattern); return 0;}

输出结果：

匹配成功，起始位置：0匹配成功，起始位置：6

---

五、KMP 算法的时间复杂度分析

步骤 时间复杂度 构建 LPS 表 O(m) 主串匹配 O(n) 总时间复杂度 O(n + m)

空间复杂度也为 O(m)，用于存储 lps 数组。

---

六、KMP 算法应用场景

• 文本编辑器中的查找替换功能
• 防火墙/入侵检测系统（IDS）中的关键字过滤
• DNA序列比对与基因分析
• 日志文件分析与日志监控
• 编译器中的词法分析阶段

---

七、总结

特性 描述 算法名称 KMP（Knuth-Morris-Pratt） 核心思想 利用已匹配信息避免主串回溯 关键结构 前缀函数（lps 数组） 时间复杂度 O(n + m) 优点 高效稳定，适合大规模数据匹配 缺点 实现相对复杂，需要预处理

---

八、参考资料

1. Knuth, D.E., Morris, J.H., & Pratt, V.R. (1977). Fast Pattern Matching in Strings.
2. GeeksforGeeks: KMP Algorithm for Pattern Searching
3. LeetCode 字符串匹配系列题目

---

📌 如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多人！欢迎关注我的博客，获取更多数据结构实战技巧。

---