超容易理解的视频

https://www.bilibili.com/video/BV18k4y1m7Ar?vd_source=7edc2de86e7ad7c7f1fb003ef155ebbb

时间复杂度O(n + m)

#include<iostream>
using namespace std;
const int N = 100010 , M = 1000010;
int n,m;
char p[N],s[M];
int ne[N];

int main()
{
    scanf("%d",&n);
    cin >> p;
    scanf("%d",&m);
    cin >> s;
    //构造ne数组
    for(int i = 1 , j = 0 ; i < n ; i ++)
    {
        while(j && p[j] != p[i]) j = ne[j - 1];
        if(p[j] == p[i]) ne[i] = j + 1 , j ++;
        else ne[i] = 0;
    }
    //kmp匹配
    for(int i = 0 , j = 0 ; i < m ; i ++)
    {
        while(j && s[i] != p[j]) j = ne[j - 1];
        if(s[i] == p[j]) j ++;
        if(j == n)
        {
            printf("%d ",i - n + 1);
            j = ne[j - 1];
        }
    }
    return 0;
}