【KMP算法C语言代码实现】在字符串匹配问题中，KMP（Knuth-Morris-Pratt）算法是一种高效的模式匹配算法，相较于传统的暴力匹配方法，它能够在最坏情况下以线性时间完成匹配过程。本文将详细介绍KMP算法的基本原理，并提供一份基于C语言的实现代码。
一、KMP算法简介
KMP算法的核心思想是利用已经匹配过的信息，避免不必要的字符比较。当发生不匹配时，它会根据之前匹配的结果调整主串和模式串的位置，从而减少重复比较的次数。
该算法的关键在于构建一个“部分匹配表”（也称为前缀函数或失败函数），用于记录模式串中每个位置的最长前缀与后缀的匹配长度。这个表可以帮助我们在匹配失败时快速跳转到合适的位置继续比较。
二、KMP算法的实现步骤
1. 构建部分匹配表（prefix数组）
- 遍历模式串，计算每个位置的最长前缀与后缀相等的长度。
2. 进行匹配操作
- 使用两个指针分别指向主串和模式串，逐个字符比较。
- 若匹配成功，则继续比较下一个字符；若失败，则根据prefix数组调整模式串的位置。
三、C语言实现代码
以下是一个完整的KMP算法实现示例：
```c
include
include
// 构建部分匹配表（prefix数组）
void buildPrefixArray(char pattern, int prefix, int len) {
int i = 0;
int j = 1;
while (j < len) {
if (pattern[i] == pattern[j]) {
prefix[j] = i + 1;
i++;
j++;
} else {
if (i != 0) {
i = prefix[i - 1];
} else {
prefix[j] = 0;
j++;
}
}
}
}
// KMP算法实现
int kmpSearch(char text, char pattern) {
int textLen = strlen(text);
int patternLen = strlen(pattern);
if (patternLen == 0) return 0;
int prefix = (int )malloc(patternLen sizeof(int));
buildPrefixArray(pattern, prefix, patternLen);
int i = 0; // text index
int j = 0; // pattern index
while (i < textLen) {
if (text[i] == pattern[j]) {
i++;
j++;
}
if (j == patternLen) {
free(prefix);
return i - j; // 返回匹配起始位置
} else if (i < textLen && text[i] != pattern[j]) {
if (j != 0) {
j = prefix[j - 1];
} else {
i++;
}
}
}
free(prefix);
return -1; // 未找到匹配
}
int main() {
char text[] = "ABABABCABABABCABAB";
char pattern[] = "ABABCABAB";
int pos = kmpSearch(text, pattern);
if (pos != -1) {
printf("Pattern found at position %d\n", pos);
} else {
printf("Pattern not found.\n");
}
return 0;
}
```
四、运行结果示例
假设输入文本为 `"ABABABCABABABCABAB"`，模式串为 `"ABABCABAB"`，程序将输出：
```
Pattern found at position 4
```
这表明模式串在主串中的第4个位置开始匹配成功。
五、总结
KMP算法通过预处理模式串，构建部分匹配表，使得在匹配过程中可以跳过不必要的比较，提高了字符串匹配的效率。在实际应用中，尤其适用于大规模数据的文本处理场景。本文提供的C语言实现代码结构清晰、逻辑严谨，便于理解与扩展。
