用c++实现KMP算法
时间: 2023-11-18 20:56:24 浏览: 33
KMP算法是一种字符串匹配算法,它的核心思想是利用已知信息来避免无效的比较,从而提高匹配效率。下面是用C++实现KMP算法的代码:
```
#include <iostream>
#include <cstring>
using namespace std;
int* getNext(string p) {
int len = p.length();
int* next = new int[len];
next[0] = -1;
int k = -1, j = 0;
while (j < len - 1) {
if (k == -1 || p[j] == p[k]) {
++k;
++j;
next[j] = k;
}
else {
k = next[k];
}
}
return next;
}
int KMP(string s, string p) {
int slen = s.length(), plen = p.length();
int i = 0, j = 0;
int* next = getNext(p);
while (i < slen && j < plen) {
if (j == -1 || s[i] == p[j]) {
++i;
++j;
}
else {
j = next[j];
}
}
if (j == plen) {
return i - j;
}
else {
return -1;
}
}
int main() {
string s = "hello world";
string p = "world";
int pos = KMP(s, p);
if (pos == -1) {
cout << "not found" << endl;
}
else {
cout << "found at position " << pos << endl;
}
return 0;
}
```
其中,getNext函数用于计算模式串p的next数组,KMP函数用于在文本串s中查找模式串p的位置。