总体思路:

pattern串与str串比较, 假设当前比较开头str坐标为p(1起点), 已经有q位比较成功
当第p+q+1位比较不相等时候, 按照暴力做法, 我们会令p++, 然后再从头开始比较, 但是通过观察我们知道,
str[p, p+q] 里面的字符跟pattern[1, q]完全相同, 如果从str[p+1]开始比较的话, 接下来的q-1次
比较(假设该轮前q-2次比较都成功了)其实就相当于从pattern取出子串[2, q]与pattern[1, q-1] 做比较
由于当前q长度是小于pattern的长度n的, 所以, 中间只要在回到str[p+q]之前有一个失败, 
这波从str[p+1]开头的重新匹配都会完全失败, 需要返回到起点, 再次p++重新开始. 
所以, 我们只需要能判断pattern的子区间[2, q]与[1, q-1]是否完全重合
就可以得知str从p+1处开始能否成功. 同理p+2, p+3之后的判断也可以仅通过观察pattern串作出判断.

所以, 假设我们在str[p+k]处成功找到pattern前缀子串了, 由于str[p+k, p+q]与pattern[1, q-k+1]完全重合,
所以我们当前在str串的指针(设为i)根本就不需要变动, 留在原地即可, 只需要令pattern里面原来在q点的指针跳回
到q-k+1处即可, 由于子串的最大相等前后缀可以通过只观察这个子串得出, 所以我们可以提前处理得到一个数组来记录
这个pattern在每个区间[1, j] 对应的"最大相等前后缀"的前缀坐标. 记为ne[j]

(结合ne生成代码看)由于我们代码是从左往右生成ne数组的, 所以第一次生成的对应的ne值是最长匹配前缀与后缀,
i如果继续往下, 如果匹配成功, 那就是顺利往右走, 当前ne数组里面前后缀映射值还是最长匹配,
                如果匹配失败, 那么也是依据已存在的ne数组先从上一步的最长匹配开始找,
所以综上, ne数组是总能找到当前pattern的后缀结尾坐标所对应最长的前缀结尾坐标

#include <stdio.h>
#define N 100010
#define M 1000010

int ne[N];
char pattern[N], str[M];

int main(void)
{
    // 1起点读取数据
    int n, m;
    scanf("%d%s%d%s", &n, pattern+1, &m, str+1);

    // ne数组的计算
    // 动态规划: 假如已知长度i-1时候的最长前缀坐标(设为j), 
    // 1. 如果pattern[j+1]与pattern[i]相等的话, 那么说明在长度为i的时候对应的ne[i]就是j+1; 
    // 2. 如果pattern[j+1]与pattern[i]不相等的话, 那就只能往j左边左再找相同的前缀了, 就是ne[j].
    // base case: 当i为1的时候为0.
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && pattern[i] != pattern[j+1]) j = ne[j];
        if (pattern[j+1] == pattern[i]) j++;
        ne[i] = j;

    }

    // kmp主体
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && str[i] != pattern[j+1]) j = ne[j];
        if (str[i] == pattern[j+1]) j++;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}