c语言实现KMP算法
时间: 2023-10-04 07:13:27 浏览: 132
KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,用于在一个主串中查找一个子串的出现位置。下面是C语言实现KMP算法的示例代码:
```c
#include <stdio.h>
#include <string.h>
void compute_lps(char* pattern, int* lps) {
int len = 0;
int i = 1;
int pattern_length = strlen(pattern);
lps[0] = 0;
while (i < pattern_length) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void kmp_search(char* pattern, char* text) {
int pattern_length = strlen(pattern);
int text_length = strlen(text);
int lps[pattern_length];
compute_lps(pattern, lps);
int i = 0;
int j = 0;
while (i < text_length) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == pattern_length) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
} else if (i < text_length && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
}
int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";
kmp_search(pattern, text);
return 0;
}
```
这段代码中,compute_lps() 函数用于计算模式串的最长公共前后缀长度数组 lps[],kmp_search() 函数用于在文本串中搜索模式串。
阅读全文