用C语言实现改进的字符串模式匹配的KMP算法。完整代码
时间: 2024-09-17 13:08:13 浏览: 55
KMP算法(Knuth-Morris-Pratt Algorithm)是一种高效的字符串搜索算法,用于在一个文本串中查找指定的模式串。它通过构建部分匹配表(也称作失配函数)避免了不必要的字符比较,提高了效率。以下是用C语言实现改进版KMP算法的部分关键代码:
```c
#include <stdio.h>
#include <string.h>
// 创建部分匹配表
void compute_lps(char pattern[], int lps[], int len) {
int i = 0, j = -1;
while (i < len) {
if (j == -1 || pattern[i] == pattern[j]) {
lps[i + 1] = ++j;
i++;
} else {
j = lps[j];
}
}
}
// KMP搜索函数
int kmp_search(char text[], char pattern[]) {
int m = strlen(text);
int n = strlen(pattern);
int lps[n];
compute_lps(pattern, lps, n);
int index = 0; // 文本起始位置
for (int i = 0; i < m; i++) {
if (index != -1 && (text[i] != pattern[index])) {
index = lps[index];
} else if (text[i] == pattern[index]) {
index++;
if (index == n) {
return i - n + 1; // 找到匹配的位置
}
}
}
return -1; // 没有找到匹配
}
int main() {
char text[] = "ABABCABADCAB";
char pattern[] = "ABC";
int result = kmp_search(text, pattern);
if (result != -1) {
printf("Pattern found at index %d\n", result);
} else {
printf("Pattern not found in the text.\n");
}
return 0;
}
```
这个代码首先计算了模式串的LPS表,然后在文本串中使用该表进行搜索。如果在搜索过程中遇到不匹配的情况,就利用失配函数来跳过多余的比较。