kmp算法c语言完整代码
时间: 2023-08-14 11:11:51 浏览: 248
kmp算法 c语言
下面是KMP算法的C语言完整代码示例:
```c
#include <stdio.h>
#include <string.h>
void computeLPSArray(char* pattern, int M, int* lps) {
int len = 0;
lps[0] = 0; // lps[0] is always 0
int i = 1;
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++;
}
}
}
}
void KMP(char* pattern, char* text) {
int M = strlen(pattern);
int N = strlen(text);
int lps[M];
computeLPSArray(pattern, M, lps);
int i = 0; // index for text[]
int j = 0; // index for pattern[]
while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == M) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";
KMP(pattern, text);
return 0;
}
```
上面的代码实现了KMP算法,通过在给定文本中查找指定模式的出现位置。在示例中,我们在字符串`text`中查找模式`pattern`的出现位置,并将其打印出来。
请注意,这只是一个简单的示例,你可以根据自己的需求进行修改和扩展。
阅读全文