kmpc++实现源代码
时间: 2024-06-22 18:02:54 浏览: 7
下面是KMP算法的C++实现源代码:
```
#include <iostream>
#include <cstring>
using namespace std;
void get_next(char s[], int next[]) {
int len = strlen(s);
int j = -1;
next[0] = -1;
for (int i = 1; i < len; i++) {
while (j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if (s[i] == s[j + 1]) {
j++;
}
next[i] = j;
}
}
int kmp(char s1[], char s2[], int next[]) {
int len1 = strlen(s1);
int len2 = strlen(s2);
int j = -1;
for (int i = 0; i < len1; i++) {
while (j >= 0 && s1[i] != s2[j + 1]) {
j = next[j];
}
if (s1[i] == s2[j + 1]) {
j++;
}
if (j == len2 - 1) {
return i - len2 + 1;
}
}
return -1;
}
int main() {
char s1[] = "ababcabcacbab";
char s2[] = "abcac";
int next[1000];
get_next(s2, next);
int pos = kmp(s1, s2, next);
cout << pos << endl;
return 0;
}
```
该代码实现了KMP算法的核心部分,包括获取next数组和KMP匹配过程。在主函数中,我们可以输入两个字符串,然后调用get_next和kmp函数进行匹配,最终输出匹配的位置。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)