算法1

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

思路

`KMP算法的思想是：在模式串和主串匹配过程中，当遇到不匹配的字符时，对于主串和模式串中已对比过相同的前缀字符串，找到长度最长的相等前缀串，从而将模式串一次性滑动多位，并省略一些比较过程。在上个例子，KMP算法中，是这样处理的：

main: “ababaeaba” // 比如main中的”ababa”子串，对标为[2~4]的”aba”和pattern中下
pattern: “ababacd” // 标为[0~2]的”aba”相同,此时可以滑动j-k位,即j=j-k。(其中j是
// pattern中”c”的下标,k是”abc”的长度)。
“ababaeaba” // 比较过程中，main[5]为”e”和pattern[5]为”c”不匹配，但是两个
“ababacd” // 串中都有相同的”aba”前缀,所以可以滑动j-k位
|
∨
“ababaeaba”
“ababacd”
| // 滑动j-k位后发现main[5]和patterb[3]不相同，需要再次滑动
∨
“ababaeaba”
“ababacd” // 滑动过程和上次类似。
通过这个例子可以看出，每次滑动的位数是j-k，滑动位数和主串无关，仅通过模式串就可以求出。在KMP算法中通过next数组来存储当两个字符不相等时模式串应该移动的位数。
`

C++ 代码

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

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

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

    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;
    }

    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);
            j = ne[j];
        }
    }

    return 0;
}