自己动手实现 KMP 算法。(串)
时间: 2023-08-05 22:04:49 浏览: 47
KMP算法是一种字符串匹配算法,它的核心思想是利用已经匹配过的信息来减少不必要的比较次数。下面是KMP算法的实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
void getNext(string p, int* next) {
int len = p.length();
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];
}
}
}
int kmp(string s, string p) {
int slen = s.length(), plen = p.length();
int i = 0, j = 0;
int* next = new int[plen];
getNext(p, next);
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() {
string s = "hello, world!";
string p = "world";
int index = kmp(s, p);
if (index != -1) {
cout << "匹配成功,匹配位置为:" << index << endl;
} else {
cout << "匹配失败" << endl;
}
return 0;
}
```
其中,getNext函数用来计算模式串p的next数组,kmp函数用来进行字符串匹配操作。在实现过程中,我们利用了一个next数组来记录已经匹配过的信息,从而减少不必要的比较次数,提高匹配效率。