帮我写一个KMP的C++实现代码
时间: 2023-02-11 15:19:33 浏览: 139
KMP算法实现的C++代码
KMP(Knuth-Morris-Pratt)算法是一种在文本串中查找模式串的算法。它通过利用已匹配的前缀和后缀来减少模式串在文本串中的比对次数,从而提高查找效率。
下面是一个 C 语言实现的 KMP 算法的代码:
```c
#include <stdio.h>
#include <string.h>
void kmp(char* T, char* P) {
int n = strlen(T);
int m = strlen(P);
int next[m];
getNext(P, next);
int i = 0, j = 0;
while (i < n) {
if (j == -1 || T[i] == P[j]) {
i++;
j++;
} else {
j = next[j];
}
if (j == m) {
printf("find at %d\n", i - m);
j = next[j];
}
}
}
void getNext(char* P, int* next) {
int m = strlen(P);
next[0] = -1;
int k = -1, j = 0;
while (j < m - 1) {
if (k == -1 || P[j] == P[k]) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
}
int main() {
char T[] = "abcabcababaccc";
char P[] = "ababa";
kmp(T, P);
return 0;
}
```
该代码实现了KMP算法的基本流程,其中主函数调用 kmp(T,P) 函数,传入文本串 T 和模式串 P,在文本串中寻找模式串并输出所在位置, next数组为next数组的数组,保存的是匹配的前缀和后缀,getNext 函数用来生成 next 数组
阅读全文