本文最后更新于31 天前，其中的信息可能已经过时，如有错误请发送邮件到wsryhc@qq.com
原理：先对于要寻找的字符串进行搜索，然后在主字符串中继续搜索。
创建一个数组ne，记录每次返回的位置。
数组输入建议从1开始，0作为跳回点。
一开始，设定j为第一个元素前的位置，设定i为第二个元素的位置，然后对于第j+1位和第i位进行判断，
如果相同，那么j++，因为如果在第i位匹配不成功时，可以跳回之前重复的位置。（如果匹配第i位时不一样，那就可以跳回第j位重新开始）更新ne数组的第i个位置为j，也就是后面如果匹配到第i个位置发现不匹配，那就可以根据ne[i]进行跳回，也就是跳回j，然后继续判断；
如果不相同，那就先检查这个j是不是在第一个元素前的位置（也就是第0位），如果不在，那就证明之前一定有相同的结果（就是前面判断相同的地方），那就可以跳回去。假设为ababc，如果匹配到了第五位c不匹配，但是之前匹配ab时，第四位记录的跳回位置为1，也就是第二位的前一位，那就可以继续从ab开始匹配（也就是第三位开始寻找，如果后面有aba这样的就可以继续寻找）。
最后对于总的字符串进行匹配，还是从0开始，但是i=1，原理同上。只要发现j走到了要查找的字符串的末尾，那就代表查找成功，返回位置。
代码
#include<iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j]; //开始先进行判断,如果不相等，就跳回上次的位置
if (p[i] == p[j + 1]) j ++ ; //如果相等，匹配的位置向后移动一位
ne[i] = j; //更新ne数组，第i个位置后如果不匹配可以跳回的位置
}
for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}
/*作者：yxc
链接：https://www.acwing.com/activity/content/code/content/43108/
来源：AcWing
*/