KMP算法怎么用C语言实现
时间: 2023-08-16 18:23:00 浏览: 65
以下是KMP算法的C语言实现,同样字符串下标从0开始:
```c
#include <stdio.h>
#include <string.h>
void getNext(char *pattern, int *next) { // 求next数组
int m = strlen(pattern);
int j = 0;
next[0] = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[j] != pattern[i]) {
j = next[j - 1];
}
if (pattern[j] == pattern[i]) {
j++;
}
next[i] = j;
}
}
int kmp(char *text, char *pattern) {
int n = strlen(text), m = strlen(pattern);
int next[m]; // next数组
getNext(pattern, next);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
return i - m + 1; // 匹配成功,返回模式串在文本串中的位置
}
}
return -1; // 匹配失败,返回-1
}
int main() {
char text[] = "ABABABCABAABABABD";
char pattern[] = "ABABABD";
int pos = kmp(text, pattern);
printf("%d\n", pos);
return 0;
}
```
其中,getNext函数用于求模式串的next数组,kmp函数用于在文本串中匹配模式串,返回模式串在文本串中第一次出现的位置,如果不存在则返回-1。在main函数中,我们可以测试kmp函数的正确性。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)