请用c++帮我实现KMP算法
以下是C++实现的KMP算法代码:
#include <iostream>
#include <cstring>
using namespace std;
// 计算next数组
void getNext(char* p, int* next, int len) {
int i = 0, j = -1;
next[0] = -1;
while (i < len) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
// KMP算法
int kmp(char* s, char* p) {
int slen = strlen(s);
int plen = strlen(p);
int* next = new int[plen];
getNext(p, next, plen);
int i = 0, j = 0;
while (i < slen && j < plen) {
if (j == -1 || s[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
delete[] next;
if (j == plen) {
return i - j;
} else {
return -1;
}
}
int main() {
char s[] = "hello world";
char p[] = "world";
int pos = kmp(s, p);
if (pos == -1) {
cout << "not found" << endl;
} else {
cout << "found at position " << pos << endl;
}
return 0;
}
原文地址: https://www.cveoy.top/t/topic/blPe 著作权归作者所有。请勿转载和采集!