// 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 ( __________ ) j ++ ;
    if (j == m){
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

Next 数组的计算过程实际上是在寻找模式串的最长公共前后缀。具体来说，对于每一个位置 i，Next[i] 存储了模式串 p 在 p[1:i]（即 p 的前 i 个字符）中最长的公共前后缀的长度。

理解Next数组、举例：

对于模式串 p = "ABABAC"，Next 数组的计算如下：

p[1:1] 没有前后缀，Next[1] = 0。 p[1:2] 的前后缀不匹配，Next[2] = 0。 p[1:3] 的前后缀为 "A"，所以 Next[3] = 1。 p[1:4] 的前后缀为 "AB"，所以 Next[4] = 2。 p[1:5] 的前后缀为 "ABA"，所以 Next[5] = 3。 p[1:6] 没有匹配的前后缀，Next[6] = 0。 因此，Next 数组本质上就是帮助我们快速找到模式串在某个位置的最长公共前后缀，从而优化字符串匹配过程。

具体例子：

题目描述

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。 第二行输入字符串 P。 第三行输入整数 M，表示字符串 S 的长度。 第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围 $1≤N≤10^5$ $1≤M≤10^6$ 输入样例：

3
aba
5
ababa

输出样例：

0 2

C++代码

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

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

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com