#include <iostream> #include <cstring> using namespace std; // 计算next数组 void getNext(char* p, int* next) { int len = strlen(p); int k = -1; int j = 0; next[0] = -1; while (j < len - 1) { if (k == -1 || p[k] == p[j]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } // KMP算法 int kmp(char* s, char* p) { int i = 0; int j = 0; int s_len = strlen(s); int p_len = strlen(p); int* next = new int[p_len]; getNext(p, next); while (i < s_len && j < p_len) { if (j == -1 || s[i] == p[j]) { ++i; ++j; } else { j = next[j]; } } if (j == p_len) { return i - j; } else { return -1; } } int main() { char s[] = "ABCDABD"; char p[] = "ABD"; int pos = kmp(s, p); cout << pos << endl; return 0; }

这段代码是实现KMP算法在字符串s中查找子串p的位置，输出的结果为2，即p在s中的起始位置为2。

具体实现过程如下：

1. 定义了一个函数getNext，用于计算模式串p的next数组，即在匹配过程中利用已经匹配过的信息，避免重复匹配，提高匹配效率。

2. 定义了一个函数kmp，用于实现KMP算法。

3. 在main函数中，定义了字符串s和p，并调用kmp函数查找p在s中的位置，输出结果为2。

需要注意的是，在getNext函数中，next[0]的初值为-1。在kmp函数中，如果j=-1或者s[i]等于p[j]，则i和j都加1；否则，j跳到next[j]的位置。如果j等于p_len，则匹配成功，返回i-j的值；否则匹配失败，返回-1。