如果看y总的视频讲解，最好看后面的，因为后面有举字符串的例子 （我感觉）
解题过程
代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int ne[N];
char s[N], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;//数组下标为1，所以是p+1 s+1
//求ne[]过程
for (int i = 2, j = 0; i <= n; i ++ )//因为ne[1]=0,使用i下标从2开始
{
//反复匹配，所以用while
while (j && p[i] != p[j + 1]) //如果j!=0(即j没有退回起点)
{
j = ne[j];//退而求其次
}
if (p[i] == p[j + 1]) j ++ ;//前进一步
ne[i] = j;
}
//kmp匹配过程
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) //如果j!=0(即j没有退回起点),并且不匹配
{ //就使用ne[]往前退
j = ne[j]; //如果退无可退(j=0)就看下一个i
}
if (s[i] == p[j + 1]) j ++ ;//如果已经匹配，那么寻找下一个
if (j == n)
{
printf("%d ", i - n);//输出起始位置
j = ne[j];//因为有左右两部分字符串匹配，所以要退回前面
}
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/131435.html
