思路

1. 模式串（小的）匹配失败的时候，不会全部回退，而是回退到最近一次可以落脚的地方

   比如我们有个模式串（小的）ababc，那么当我匹配到c失败的时候，我可以将模式串下标(j)回退到初始位置，然后字符串下标回退到开始匹配的起点的下一个位置（无法理解可以模拟一下暴力过程）

   但是此时，abab这个东西就会引起我们的注意，既然是在c的位置出的问题，就表明前面的完全没问题，那假设我们仅仅向后挪动一个，那么下次匹配的就是b和a进行比较，必定失败。我们将模式串看作钥匙，带齿的，每个字母代替一种高度，当abab匹配完成的时候，我们已经可以看到它的大致形状，像玩游戏一样，我们如果能看到钥匙的形状，那么一定会主动向后挪动两个位置，即让a1b1放到a2b2的位置。如果我们的模式串是abababababc呢，我们会主动向后移动8个位置。

   同时，向后移动并不是仅仅为了寻找有效地址，而是因为到c的时候，向后移动模式串，此时无法匹配钥匙形状的位置，是没有希望的，前途黑暗的，因为后路被自己就封死了。

   大概就这么个意思，思路还是很简单的，主要的代码简短，比较抽象

Debug

1. 边界，两层while都要控制i的边界，不然内层会爆掉i
2. 输出判断，当内层i>m时，会出循环，但是此时会输出，与预测不符；真正符合输出的是j读到结尾，即

    if (j > n)
    {
        cout << ;
    }

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

char p[N];
char s[M];
int nxt[N];

void kmp(int n, int m)
{
    nxt[1] = 0;
    int i, k, j;
    i = 1;
    k = 0;

    while (i <= n)
    {
        if (!k || p[i] == p[k]) nxt[++i] = ++k;
        else k = nxt[k];
    }

    i = j = 1;

    while (i <= m)
    {
        while (j <= n && i <= m) {
            if (!j || p[j] == s[i]) ++i, ++j;
            else j = nxt[j];
        }
        if (j > n)
        {
            cout << i - j << " ";
            j = nxt[j];
        }
    }

    return ;
}

int main()
{
    int n, m;

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }

    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
    }

    kmp(n, m);

}

/*
100
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7x
500
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNA6fQNNluS6Uo12Lhd2UMUVm8bd6xNhNNyg1SNvvKvavJGn77RNjqBNNNg2UUUfkLLLs8Q47B85u8jrNeNNqWxAzvB9Sgv9vBfxnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNVF3NVsgUOUUxjULxAU44PU788P8se0LNpSfffvvkvvvnKyosnNEN2KNNgU3OUxkLuLLx44vixt08OsNNNN5ZtAfvOvsvivpv72

0 100 300
*/

/*
10
jNNNNjNNNN
30
jNNPw9NNNNnNMANTNHGNjNNNNjNNNN

20
*/