kmp算法C语言实现
时间: 2023-12-25 17:26:58 浏览: 38
以下是KMP算法的C语言实现:
```c
#include <stdio.h>
#include <string.h>
void getNext(char* p, int* next) {
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1) {
if (k == -1 || p[j] == p[k]) {
++j;
++k;
if (p[j] != p[k]) {
next[j] = k;
} else {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
void kmp(char* s, char* p) {
int sLen = strlen(s);
int pLen = strlen(p);
int* next = new int[pLen];
getNext(p, next);
int i = 0;
int j = 0;
while (i < sLen && j < pLen) {
if (j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == pLen) {
printf("匹配成功,位置为:%d\n", i - j);
} else {
printf("匹配失败\n");
}
delete[] next;
}
int main() {
char s[] = "BBC ABCDAB ABCDABCDABDE";
char p[] = "ABCDABD";
kmp(s, p);
return 0;
}
```