前言：先看一下朴素做法

for (int i = 1; i <= n; i ++ )
{
    bool flag = true;
    for (int j = 1; j <= m; j ++ )
    {
        if (s[i + j - 1] != p[j])
        {
            flag=false;
            break;
        }
    }
}

KMP算法：

next[]数组定义：

前i个字母构成的字符串中，最长的与前缀相等的后缀长度.

举例：abaabc next[5]=2 -> ab与ab

具体优化过程：(下标从0开始从1开始都可以，笔试模拟一般都是从0开始)

P:   abaababaabcabaa     
s:   abaabc
下标:012345

简述：匹配到下标为5的位置时不匹配而结束，
那么可以根据next[]前缀后缀匹配跳转，
直接跳转到匹配不相等的位置前面有next[5]长度位置上，
省略很多匹配操作，如下：（主要还是自己去学会模拟整个过程）

P:   abaababaabcabaa
s:   abaabc
s:      abaabc
下标:012345

next[]数组的建立过程也就是自己匹配自己的过程，跟上面类似；

如果，你KMP实在搞不懂，推荐你看这个大佬的讲解：

困扰已久的KMP https://www.acwing.com/blog/content/440/

实现王道书上的构建next数组写法

void get_next(char* p,int* ne)
{
    int i = 1, j = 0;
    ne[1] = 0;
    while(i < n)
    {
        if(j == 0 || p[i] == p[j])
        {
            i ++;
            j ++;
            ne[i] = j;
        }
        else    j = ne[j];
    }
}

实现王道书上的子母串KMP写法：

void Index_KMP(char* s,char* p,int* ne)
{
    int i = 1, j = 1;
    while(i <= m && j <= n) //n是子串长度，m是母串长度
    {
        if(j == 0 || s[i] == p[j])
        {
            i ++;
            j ++;           //继续比较后继字符
        }
        else    j = ne[j];  //模式串向右移动
    }
    if(j > n)
        return i - n;       //匹配成功
    else
        return 0;
}

实现王道书上的nextval写法：

void get_nextval(char* p,int* nextval)
{
    int i = 1, j = 0;
    nextval[1] = 0;
    while(i < n)
    {
        if(j == 0 || p[i] == p[j])
        {
            j ++;i++;
            if(p[i] != p[j])    nextval[i] = j;
            else    nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

代码：（如果，你理解前缀后缀动态维护的话，可以学这种方法精简版）

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 100010
#define M 1000010
using namespace std;

int n,m;
char p[N], s[M];
int ne[N];  //next[]数组缩写ne[]数组

int main()
{
    //从下标为1开始的这种写法，代码更短
    scanf("%d%s", &n, p + 1);
    scanf("%d%s", &m, s + 1);

    for (int i = 2, j = 0;i <= n; i ++) //next[1]不需要求
    {
        while (j && p[i] != p[j + 1])   j = ne[j];
        if(p[i] == p[j + 1])    j ++;
        ne[i] = j;
    }

    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);
    }
    return 0;
}

//这种写法代码短,在实际运行效果中可能多一两次,但完全不影响运算集

下标从0开始的写法（不推荐）

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
char s[N], p[N];
int ne[N];

int main()
{
    cin >> m >> p >> n >> s;

    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ )
    {
        while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < n; i ++ )
    {
        while (j != -1 && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m - 1)
        {
            cout << i - j << ' ';
            j = ne[j];
        }
    }

    return 0;
}