【KMP算法的C语言程序】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能够在O(n + m)的时间复杂度内完成模式串与主串的匹配，其中n为主串长度，m为模式串长度。相比传统的暴力匹配方法，KMP算法通过预处理模式串，构建部分匹配表（也称为“失败函数”或“前缀函数”），从而避免了不必要的字符比较。
一、KMP算法原理简述
KMP算法的核心思想是利用已匹配的部分信息，避免重复比较。当在某个位置发生不匹配时，不是将主串指针回退，而是根据部分匹配表调整模式串的位置，继续进行匹配。
二、KMP算法步骤
1. 构建部分匹配表（next数组）
- 遍历模式串，计算每个位置的最长前缀和后缀的长度。
2. 匹配过程
- 使用两个指针分别指向主串和模式串。
- 当字符匹配时，两个指针同时后移。
- 当字符不匹配时，根据next数组调整模式串的位置，主串指针不回退。
三、C语言实现代码
以下是一个KMP算法的C语言实现示例：
```c
include
include
// 构建next数组
void buildNext(char pattern, int next) {
int len = strlen(pattern);
next[0] = 0; // 第一个字符的前缀和后缀长度为0
int j = 0;
for (int i = 1; i < len; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
}
// KMP算法实现
void kmpSearch(char text, char pattern) {
int n = strlen(text);
int m = strlen(pattern);
int next = (int )malloc(m sizeof(int));
buildNext(pattern, next);
int i = 0; // text指针
int j = 0; // pattern指针
while (i < n) {
if (pattern[j] == text[i]) {
i++;
j++;
} else {
if (j != 0) {
j = next[j - 1];
} else {
i++;
}
}
if (j == m) {
printf("匹配成功，起始位置为 %d\n", i - j);
j = next[j - 1]; // 继续查找下一个可能的匹配
}
}
free(next);
}
```
四、性能对比表格
| 项目 | 暴力匹配 | KMP算法 |
| 时间复杂度 | O(nm) | O(n + m) |
| 是否需要预处理 | 否 | 是 |
| 主串指针是否回退 | 是 | 否 |
| 空间复杂度 | O(1) | O(m) |
| 适用场景 | 小规模数据 | 大规模数据、频繁匹配 |
五、总结
KMP算法通过构建next数组，有效减少了重复比较的次数，提高了字符串匹配的效率。在实际应用中，尤其是在需要多次匹配同一模式串的情况下，KMP算法具有明显优势。其C语言实现相对简洁，逻辑清晰，适合用于教学或实际开发中。
