分享一篇博客有关KMP的详细介绍数据结构KMP算法配图详解（超详细）_哈顿之光的博客-CSDN博客_数据结构kmp算法详解

题目：

代码：

#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;  //下标从1开始

    //求next过程（与kmp匹配过程类似）
    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;
    }

    //kmp匹配过程
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];   //j没有退回起点并且不能和当前s[i]匹配时，使j=ne[j]即j往前退一步，直到匹配为止或者j退到开头
        if (s[i] == p[j + 1]) j ++ ;   //判断while()结束条件：当因为匹配结束时，j移到下一位置
        if (j == n)   //匹配成功
        {
            printf("%d ", i - n);  //输出起始位置
            j = ne[j];    //匹配成功再往前退一步
        }
    }

    return 0;
}

动画演示视频KMP模式搜索算法动画演示_哔哩哔哩_bilibili