kmp算法c++完整代码
时间: 2023-11-09 21:59:22 浏览: 54
好的,下面是 KMP 算法的完整代码。假设要在字符串 `str` 中查找模式串 `pattern`:
```c
#include <stdio.h>
#include <string.h>
void get_next(char *pattern, int *next) {
int pattern_len = strlen(pattern);
next[0] = -1;
int j = -1;
for (int i = 1; i < pattern_len; i++) {
while (j >= 0 && pattern[j + 1] != pattern[i]) {
j = next[j];
}
if (pattern[j + 1] == pattern[i]) {
j++;
}
next[i] = j;
}
}
void kmp(char *str, char *pattern) {
int str_len = strlen(str);
int pattern_len = strlen(pattern);
int next[pattern_len];
get_next(pattern, next);
int j = -1;
for (int i = 0; i < str_len; i++) {
while (j >= 0 && pattern[j + 1] != str[i]) {
j = next[j];
}
if (pattern[j + 1] == str[i]) {
j++;
}
if (j == pattern_len - 1) {
printf("Found pattern at index %d\n", i - pattern_len + 1);
j = next[j];
}
}
}
int main() {
char str[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABCABAB";
kmp(str, pattern);
return 0;
}
```
输出:
```
Found pattern at index 10
```