代码
#include<bits/stdc++.h>
using namespace std;int Next[100001] = { 0 };void getNext(string p, int* Next)
{Next[0] = -1;int len = p.length();int k = -1; // 前缀int j = 0; // 后缀while (j < len - 1){if (k == -1 || p[k] == p[j])// k==-1：起始{k++;j++;Next[j] = k;}else if (p[k] != p[j]){k = Next[k];}}}int KMP(string t, string p, int* Next)
{int len1 = t.length();int len2 = p.length();int i = 0, j = 0;while (i < len1 && j < len2){if (j == -1 || t[i] == p[j])// j==-1：为了找到第一个匹配字符而不断右移// 或成功匹配{i++;j++;}else if (t[i] != p[j]){j = Next[j];}}if (j == len2) // 找到return i - j;elsereturn -1;}int main()
{string t, p;cin >> t >> p;getNext(p, Next);int pos = KMP(t, p, Next);cout << pos << endl;int i = 0;for (; i < p.length() - 1; i++)cout << Next[i] << ' ';cout << Next[i] << endl;system("pause");return 0;
}
优化Next数组后的代码如下，不过这样会使得Next数组的值不满足要求（虽然有提速
在这里插入代码片#include<bits/stdc++.h>
using namespace std;// 提速后的方法，但会使next数组值不满足条件
int Next[100001] = { 0 };void getNext(string p, int* Next)
{Next[0] = -1;int len = p.length();int k = -1; // 前缀int j = 0; // 后缀while (j < len - 1){if (k == -1 || p[k] == p[j])// k==-1：起始{k++;j++;// Next[j] = k;if (p[j] == p[k])// 若跳回next[j]=k处，事实上在比较同一字符，必然失配// 所以直接返回next[k]处，略过一次匹配{Next[j] = Next[k];}else{Next[j] = k;}}else if (p[k] != p[j]){k = Next[k];}}}int KMP(string t, string p, int* Next)
{int len1 = t.length();int len2 = p.length();int i = 0, j = 0;while (i < len1 && j < len2){if (j == -1 || t[i] == p[j])// j==-1：为了找到第一个匹配字符而不断右移// 或成功匹配{i++;j++;}else if (t[i] != p[j]){j = Next[j];}}if (j == len2) // 找到return i - j;elsereturn -1;}int main()
{string t, p;cin >> t >> p;getNext(p, Next);int pos = KMP(t, p, Next);cout << pos << endl;int i = 0;for (; i < p.length() - 1; i++)cout << Next[i] << ' ';cout << Next[i] << endl;system("pause");return 0;
}