第一种形式（数据结构严蔚敏版）
（字符串下标均从1开始）
先上代码：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int Next[100];
char S[100],T[100];
vector<int> ans;
int main()
{
int n,m;
cin>>n>>m;
cin>>S+1>>T+1;
//求Next数组
int i = 1,j = 0;
Next[1] = 0;
while(i<=m)
{
if(j==0 || T[i] == T[j])
{
++i,++j;
Next[i] = j;
}
else
j = Next[j];
}
/*
for(int i = 1 ; i<=m ; i++)
cout<<Next[i]<<" ";
cout<<endl;
*/
//主串与模式串开始匹配
cout<<endl;
i = 1,j = 1;
while(i<=n)
{
if(j==0 || T[j] == S[i] && i+1<=n)
{
++i,++j;
}
else
j = Next[j];
if(j==m)
{
ans.push_back(i-m+1);
j = Next[j];
}
}
int k = 0;
while(k<ans.size())
{
cout<<ans[k++]<<" ";
}
return 0;
}
思路
在该程序中，主串的 i 与 j 同时从1开始遍历，j 等于 0 的情况表示需要模板串从头开始与主串匹配，j 不等于 0 时则 i 与 j 同时遍历并判断是否匹配，若失配，i 固定不回溯，模板串向前移动（ j = Next[ j ];）重复此过程，当 j 等于 模板串的长度时，说明在主串中存在此模板串，记录位置，模板串继续移动（ j = Next[ j ]; ) ，继续匹配。
第二种形式
上代码：
#include <iostream>
using namespace std;
const int N = 10010,M = 100010;
//p为模板串，s为主串
int n,m;
char p[N],s[M];
int Next[N];
int main()
{
cin>>n>>p+1>>m>>s+1;
Next[1] = 0;
for(int i = 2,j = 0; i<=n ; i++)
{
while(j && p[i] != p[j+1]) j = Next[j];
if(p[i] == p[j+1]) ++j;
Next[i] = j;
}
/*
for(int i = 1;i<=n;i++)
cout<<Next[i]<<" ";
cout<<endl;
*/
for(int i = 1,j = 0; i<=m ; i++)
{
while(j && s[i]!=p[j+1]) j = Next[j];
if(s[i] == p[j+1]) ++j;
if(j == n)
{
cout<<i-n<<" ";
j = Next[j];
}
}
return 0;
}
思路
此代码与第一种形式的区别就在于求Next数组上，第一种是忽略当前位置，再当前位置前的串中求最长相同前缀后缀，将此长度+1并记录到Next数组中，因为在第一个代码中，i 与 j 都是从1开始遍历，当 j = Next[ j ] 后，直接将 i 与 j对比，而第二种形式种，求Next数组时，是观察包括当前位置的串种最长的相同前缀后缀，并直接记录在Next数组种，因为第二种代码中，i 从1开始，j 从0开始，每次对比的是 i 与 j + 1；所以当在匹配过程中发生失配时，j = Next[ j ] 实际是当前位置（i 或 j+1）的前一个位置的最长相同前缀后缀，j + 1 后 与 i 对比，实际上与第一种形式相同，但我认为这是两种不同的记录方式。
看完KMP算法，真的是敬佩三位科学家，另外，在学习过程中也遇到了很多困难，目前，对该算法的理解也只是很片面，浅显，继续努力！！！
更新一道例题，来源leetcode181场周赛
5367. 最长快乐前缀
「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
输入：s = "level"
输出："l"
解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
输入：s = "ababab"
输出："abab"
解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
输入：s = "a"
输出：""
对该字符串求next数组，然后对按next[s.size()]更新答案即可
const int N = 1e5+100;
int ne[N];
class Solution {
public:
//求next数组
void KMP(string s)
{
string t = " " + s;
int n = t.size(); //下标从1开始
ne[1] = 0;
for(int i = 2,j = 0; i<=n; i++)
{
while(j && t[i] != t[j+1]) j = ne[j];
if(t[i] == t[j+1]) ++j;
ne[i] = j;
}
}
string longestPrefix(string s) {
KMP(s);
int n = s.size();
string ans = "";
for(int i = 0; i<ne[n]; i++) ans += s[i];
return ans;
}
};
