c++实现KMP算法的代码
时间: 2023-03-29 09:03:50 浏览: 151
以下是 C 语言实现 KMP 算法的代码:
```c
#include <stdio.h>
#include <string.h>
void getNext(char* pattern, int* next) {
int len = strlen(pattern);
next[] = -1;
int k = -1;
int j = ;
while (j < len - 1) {
if (k == -1 || pattern[j] == pattern[k]) {
++j;
++k;
if (pattern[j] != pattern[k]) {
next[j] = k;
} else {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
int kmp(char* text, char* pattern) {
int i = ;
int j = ;
int text_len = strlen(text);
int pattern_len = strlen(pattern);
int next[pattern_len];
getNext(pattern, next);
while (i < text_len && j < pattern_len) {
if (j == -1 || text[i] == pattern[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == pattern_len) {
return i - j;
} else {
return -1;
}
}
int main() {
char text[] = "ABABABABCABAAB";
char pattern[] = "ABABCABAA";
int pos = kmp(text, pattern);
printf("%d\n", pos);
return ;
}
```
希望能对您有所帮助。
阅读全文