为了方便你创建 OJ 测试数据，我编写了一个完整的数据生成器。它采用 C++14 标准，包含了 数据构造逻辑 和 标准 KMP 参考解法，可以自动生成 1.in/1.out 到 10.in/10.out。

数据生成策略说明

为了在保证强度的前提下控制文件大小（接近 2MB），我对 $S_2$ 的长度进行了合理分配。

• Case 1-3 (入门级)：小规模随机数据。
• Case 4-5 (特殊构造)：针对暴力算法的“杀手锏”。例如 $S_1 = \text{"AAAA...A"}$, $S_2 = \text{"AAAA...B"}$。
• Case 6-7 (高频匹配)：$S_2$ 在 $S_1$ 中大量重叠出现。
• Case 8-10 (极限规模)：$|S_1|$ 达到 $10^6$，但为了控制 .out 文件中 next 数组的大小，我们将 $|S_2|$ 稍微控制在 $2 \times 10^5 \sim 3 \times 10^5$ 左右（如果 $S_2$ 也是 $10^6$，单单输出 $10^6$ 个数字就会让文件超过 6MB）。

数据生成器代码 (gen.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

// KMP参考解法：用于生成 .out 文件
void solve_kmp(const string& s1, const string& s2, const string& out_name) {
    ofstream fout(out_name);
    int n = s1.length();
    int m = s2.length();
    
    // 构造 next 数组 (下标从0开始版本)
    vector<int> nxt(m);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && s2[i] != s2[j]) j = nxt[j - 1];
        if (s2[i] == s2[j]) j++;
        nxt[i] = j;
    }

    // 匹配过程
    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && s1[i] != s2[j]) j = nxt[j - 1];
        if (s1[i] == s2[j]) j++;
        if (j == m) {
            fout << (i - m + 2) << "\n"; // 输出 1-indexed 位置
            j = nxt[j - 1];
        }
    }

    // 输出 next 数组
    for (int i = 0; i < m; ++i) {
        fout << nxt[i] << (i == m - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

// 随机字符串生成
string gen_random(int len, int charset_size) {
    string s = "";
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 0; i < len; ++i) {
        s += (char)('A' + rng() % charset_size);
    }
    return s;
}

int main() {
    struct TestCase {
        int n, m;
        int charset;
        string type;
    };

    vector<TestCase> cases = {
        {100, 10, 26, "random"},          // 1. 小规模
        {1000, 100, 3, "random"},         // 2. 中规模，小字符集
        {5000, 5000, 2, "periodic"},      // 3. 循环节
        {100000, 100000, 1, "killer"},    // 4. 暴力算法杀手 (全A)
        {500000, 1000, 1, "killer2"},     // 5. 暴力算法杀手 (AAAA...B)
        {1000000, 2, 2, "high_freq"},     // 6. 极高频率匹配
        {1000000, 100, 26, "random"},     // 7. 大规模 $S1$, 小规模 $S2$
        {1000000, 200000, 26, "random"},  // 8. 极限数据1 (随机)
        {1000000, 300000, 2, "random"},   // 9. 极限数据2 (小字符集)
        {1000000, 300000, 2, "overlap"}   // 10. 极限数据3 (高度重叠)
    };

    for (int i = 0; i < cases.size(); ++i) {
        string in_name = to_string(i + 1) + ".in";
        string out_name = to_string(i + 1) + ".out";
        string s1, s2;
        int n = cases[i].n, m = cases[i].m;

        if (cases[i].type == "random") {
            s1 = gen_random(n, cases[i].charset);
            s2 = gen_random(m, cases[i].charset);
        } else if (cases[i].type == "periodic") {
            string unit = gen_random(10, cases[i].charset);
            while (s1.length() < n) s1 += unit;
            while (s2.length() < m) s2 += unit;
            s1 = s1.substr(0, n); s2 = s2.substr(0, m);
        } else if (cases[i].type == "killer") {
            s1 = string(n, 'A');
            s2 = string(m, 'A');
        } else if (cases[i].type == "killer2") {
            s1 = string(n, 'A');
            s2 = string(m - 1, 'A') + "B";
        } else if (cases[i].type == "high_freq") {
            s1 = string(n, 'A');
            s2 = "AA";
        } else if (cases[i].type == "overlap") {
            s1 = "";
            while(s1.length() < n) s1 += "ABABA";
            s1 = s1.substr(0, n);
            s2 = "ABABA";
        }

        // 写入 .in 文件
        ofstream fin(in_name);
        fin << s1 << "\n" << s2 << endl;
        fin.close();

        // 生成 .out 文件
        solve_kmp(s1, s2, out_name);
        cout << "Generated Case " << i + 1 << endl;
    }

    return 0;
}

性能与复杂度优化思考

1. 时间复杂度优化：

   • 生成过程：生成器本身采用 $O(N+M)$ 的参考算法，即使 $N=10^6$，生成 10 组数据总时间也在 1-2 秒内。
   • 剪枝/避免重复：在生成“杀手锏”数据（如全 'A'）时，直接使用 string(n, 'A') 构造函数，避免逐个字符循环。

2. 空间复杂度分析：

   • 内存占用：程序中使用了 std::string 和 std::vector<int> 存储 $10^6$ 级别的数据。
   • 每个 int 4 字节，每个 char 1 字节。对于 $10^6$ 规模，大约占用 $1MB + 1MB + 4MB = 6MB$ 内存。完全不会触碰 128MB 的上限。
   • 非递归处理：KMP 算法本身是迭代实现（while 循环），不涉及深层递归，无需担心爆栈。

3. 文件大小控制：

   • 问题所在：KMP 题目要求输出模式串 $S_2$ 的每一个 $next$ 值。如果 $|S_2| = 10^6$，输出文件将包含一百万个整数。按每个整数平均 4 字节（含空格）计算，单文件大小会达到 4-6 MB。
   • 对策：在测试点 8-10 中，我将 $|S_2|$ 设置为 $3 \times 10^5$。这足以触发大部分 $O(N \cdot M)$ 算法的 TLE，同时保持 .out 文件在 2MB 左右的理想范围内。

4. 异常处理：

   • 除以0：本算法仅涉及加减法和赋值，不涉及除法。
   • 空输入：题目保证 $|S_1|, |S_2| \ge 1$，因此不考虑空串。

如何使用

1. 复制上述代码保存为 gen.cpp。
2. 使用命令编译：g++ gen.cpp -o gen -O2 -std=c++14。
3. 运行 ./gen。
4. 当前目录下会生成 1.in, 1.out ... 10.out。你可以将这些文件打包上传至你的 OJ 系统。

你好！作为教练，我将带你走过从“暴力枚举”到“KMP 算法”的思维演变过程。在 NOI 竞赛中，理解算法的演进比死记硬背模板更重要。

第一阶段：暴力匹配算法 (Brute Force)

这是最直观的想法：枚举 $S_1$ 中的每一个可能的起点，尝试与 $S_2$ 匹配。

代码实现：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/**
 * 暴力求解 KMP 模板题
 * 时间复杂度分析：
 * 1. 匹配过程：O(N * M)
 * 2. next 数组生成：O(M^3) -> 每个位置 i 枚举 L (O(M))，每次对比字符串 (O(M))
 * 空间复杂度：O(N + M)
 * 适用场景：仅能通过 20% 左右的极小规模数据
 */

int main() {
    // 优化 IO 性能
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s1, s2;
    if (!(cin >> s1 >> s2)) return 0;

    int n = s1.length();
    int m = s2.length();

    // --- 1. 暴力匹配 ---
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (s1[i + j] != s2[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            cout << i + 1 << "\n"; // 输出 1-indexed 位置
        }
    }

    // --- 2. 暴力求解 next 数组 ---
    // next[i] 定义：s2 前 i 个字符构成的子串中，最长公共真前后缀的长度
    vector<int> nxt(m + 1, 0); 
    for (int i = 1; i <= m; ++i) {
        string sub = s2.substr(0, i); // 当前处理的前缀子串
        // 枚举 Border 的长度 L，从 i-1 开始尝试（真前后缀长度必须小于子串长度 i）
        for (int L = i - 1; L >= 1; --L) {
            // 前缀：sub.substr(0, L)
            // 后缀：sub.substr(i - L, L)
            if (sub.substr(0, L) == sub.substr(i - L, L)) {
                nxt[i] = L;
                break; // 找到最长的就跳出
            }
        }
    }

    // 按题目要求输出 next 数组
    for (int i = 1; i <= m; ++i) {
        cout << nxt[i] << (i == m ? "" : " ");
    }
    cout << endl;

    return 0;
}

• 时间复杂度分析：最坏情况下（如 $S_1 = \texttt{AAAAA}$, $S_2 = \texttt{AAAAB}$），每次都要比对 $M$ 次，总复杂度 $O(N \times M)$。
• 空间复杂度：$O(N + M)$，仅需存储字符串。

为什么这个暴力版本会很慢？（启发式思考）

请观察 next 数组的暴力求解过程：

1. 重复比较：在计算 nxt[i] 时，我们完全忽略了 nxt[i-1] 的计算结果。
2. 字符串拷贝：substr() 函数会产生 $O(M)$ 的额外开销。
3. 盲目枚举：我们从 $L = i-1$ 往下减，实际上很多 $L$ 是根本不可能成立的。

时间复杂度优化建议 (从暴力到 KMP)

为了从 $O(M^3)$ 进化到 $O(M)$，我们需要三个核心跨越：

1. 利用继承性：如果 $S_2[1 \dots i-1]$ 有一个长度为 $k$ 的 Border，那么当 $S_2[i] == S_2[k+1]$ 时，nxt[i] 至少可以是 $k+1$。
2. 利用传递性 (关键回退)：如果 $S_2[i] \neq S_2[k+1]$，我们不需要把 $k$ 降为 0，而是寻找“Border 的 Border”。这就是 k = nxt[k] 的由来。
3. 双指针化：将对比字符串的操作简化为单字符对比。

第二阶段：标准 KMP 算法 (Optimal)

为了优化，我们需要消除重复比对。KMP 的精髓在于：当失配发生时，利用已经匹配过的信息，将模式串向右“跳跃”到合理的位置。

代码实现 (C++14 标准)： 这里采用竞赛常用的“下标从 1 开始”的读入技巧，可以简化逻辑。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

// 定义最大长度，1e6 级别
const int MAXN = 1000005;

char s1[MAXN], s2[MAXN];
int nxt[MAXN]; // next 数组，表示前 i 个字符的最长公共前后缀长度

int main() {
    // 使用 scanf 提高读入效率，处理 10^6 级别数据
    // s1 + 1 表示从数组下标 1 开始存储字符
    if (scanf("%s", s1 + 1) == EOF) return 0;
    if (scanf("%s", s2 + 1) == EOF) return 0;

    int n = strlen(s1 + 1);
    int m = strlen(s2 + 1);

    // --- 第一步：预处理 s2 的 next 数组 (自匹配) ---
    // nxt[1] 默认为 0，循环从 2 开始
    for (int i = 2, j = 0; i <= m; ++i) {
        // 如果不匹配，j 回退到上一个 Border 的位置
        while (j > 0 && s2[i] != s2[j + 1]) {
            j = nxt[j];
        }
        // 如果匹配成功，Border 长度加 1
        if (s2[i] == s2[j + 1]) {
            j++;
        }
        nxt[i] = j;
    }

    // --- 第二步：s1 与 s2 进行匹配 ---
    for (int i = 1, j = 0; i <= n; ++i) {
        // 如果当前字符不匹配，s2 的指针 j 回退
        while (j > 0 && s1[i] != s2[j + 1]) {
            j = nxt[j];
        }
        // 匹配成功，j 向后移
        if (s1[i] == s2[j + 1]) {
            j++;
        }
        // 如果 j 达到了 s2 的长度，说明找到了一个完整匹配
        if (j == m) {
            printf("%d\n", i - m + 1);
            // 关键：寻找下一个匹配时，j 也要回退
            j = nxt[j];
        }
    }

    // --- 第三步：按格式输出 next 数组 ---
    for (int i = 1; i <= m; ++i) {
        printf("%d%c", nxt[i], i == m ? '\n' : ' ');
    }

    return 0;
}

关键点/易错点注释：

1. 下标偏移：s2[j + 1] 的写法前提是 j 代表当前已经匹配成功的长度。当匹配 i 位置时，我们尝试看 s2 的第 j+1 个字符是否匹配。
2. While 循环回退：while (j > 0 && ...) 必须是 while 而不是 if。因为一次回退可能依然不匹配，需要连续回退。
3. 匹配成功后的 j：当 j == m 时，必须执行 j = nxt[j]。这是为了处理重叠匹配的情况（如 AAAAA 中找 AAA）。

三、 复杂度分析思考过程

1. 时间复杂度

• 预处理 $nxt$ 数组：$O(M)$。
• 主匹配过程：$O(N)$。
• 为什么是线性的？ 虽然里面有 while 循环，但我们观察 j 指针。j 只有在 j++ 时才会增加，且每次外层循环最多增加 1。j 在 while 循环中减小，但减小的总量不可能超过增加的总量。因此 j 的总变动次数是 $O(N)$ 级别的。
• 结论：总时间复杂度为 $O(N + M)$。

2. 空间复杂度

• 数组存储：$S_1, S_2$ 各需 $10^6$ 字节，nxt 数组需 $10^6$ 个 int。
• 计算：$(1 \times 2 + 4) \times 10^6 \approx 6 \text{ MB}$。
• 结论：远低于 128MB 的限制。

四、 读题理解关键词

在做字符串匹配类题目时，要快速抓取以下关键词：

1. “子串” vs “子序列”：
   • 子串必须是连续的（KMP 处理的对象）。
   • 子序列可以不连续（通常使用 DP 处理）。
2. “所有出现位置”：
   • 预示着匹配成功后不能终止，需要利用 nxt 数组继续跳转。
3. “前后缀” 或 “Border”：
   • 如果题目提到某个字符串的前缀等于后缀，哪怕没有明说 KMP，也要立刻想到 next 数组的性质。
4. “循环节”：
   • KMP 有一个经典推论：如果 $L - nxt[L]$ 能整除 $L$，则该字符串存在循环节，长度为 $L - nxt[L]$。

五、 优化建议

1. I/O 优化：在处理 $10^6$ 级别的数据时，std::cin 会非常慢。务必使用 scanf 或 std::ios::sync_with_stdio(false); cin.tie(0);。
2. 字符集优化：如果字符集很小（比如只有 A/B/C），有时可以用自动机优化，但 KMP 的通用性最强。
3. 内存连续性：在 NOI 中，尽量开全局数组而不是在函数内开大数组，防止栈溢出。

这就是 KMP 算法的完整演进。建议你在纸上对 ABABABC 模拟一下 next 数组的生成过程，你会对那个 while 回退有更深的理解！

你好！我是你的 OI 教练。今天我们要攻克的是字符串领域的一座里程碑——KMP 算法。这不仅是模板题，更是理解“状态机”和“自匹配”思想的绝佳机会。

一、 预备知识点总结

在动手写代码前，请确保你已经理解并掌握了以下概念：

1. 字符串基础：子串（Substring）与前缀/后缀（Prefix/Suffix）的区别。
2. 真前缀与真后缀：不包含字符串本身的特殊前缀和后缀。
3. Border（边界）的概念：若一个字符串的一个真前缀同时也是它的真后缀，我们称这个前缀为该字符串的一个 Border。
4. 均摊时间复杂度分析：理解为什么双指针虽然有回退，但总复杂度仍是线性的。

二、 启发式思路引导：在草稿纸上模拟

假设我们要在大串 $S_1$ 中找小串 $S_2$。

1. 暴力思想的瓶颈

如果我们逐位比对，一旦遇到不匹配（失配），就要把 $S_2$ 向后移动一位，从头开始。

• 思考：能不能利用已经匹配过的部分信息，不要让 $S_2$ 每次都回到起点？

2. “跳跃”的智慧

观察 $S_2$ 的性质。假设 $S_2 = \texttt{ABABA}$：

• 当我们在第 5 位匹配失败时，说明前 4 位 $\texttt{ABAB}$ 是匹配成功的。
• $\texttt{ABAB}$ 的最长 Border 是 $\texttt{AB}$。
• 这意味着我们可以直接把 $S_2$ 的前缀 $\texttt{AB}$ 移动到之前后缀 $\texttt{AB}$ 的位置，而不需要从头比对。

3. 绘制草稿纸推演图

请拿出纸笔，按照以下步骤画图：

• Step A: 画出 $S_1$ 和 $S_2$ 对齐的状态。
• Step B: 标记出失配位置 $i$。
• Step C: 观察 $S_2[1 \dots j]$ 这个已匹配部分。找到它的最长相等前后缀。
• Step D: 移动 $S_2$，使得前缀对齐到刚才后缀的位置。

三、 时间与空间复杂度思考

• 空间复杂度：我们需要存储 $S_1$、$S_2$ 以及一个辅助数组 $next$（或称 $pi$ 数组）。
  • $O(|S_1| + |S_2|)$，对于 $10^6$ 的数据量，大约占用几十 MB，完全符合 128MB 限制。
• 时间复杂度：
  • 直观感受：指针 $j$ 虽然会回退，但 $j$ 的增加操作在循环中总计只发生了 $|S_1|$ 次。由于 $j$ 减少的总量不可能超过增加的总量，因此回退的总次数也是 $O(|S_1|)$。
  • 结论：$O(|S_1| + |S_2|)$。

四、 算法流程图 (C++14 标准思路)

为了避免 Mermaid 语法解析错误，我们用括号描述节点内容。

graph TD
    Start(开始) --> Input(读取 S1 和 S2)
    Input --> Preprocess(预处理 S2 的 next 数组)
    
    subgraph "Next 数组构建 (自匹配)"
    Preprocess --> J0(j = 0)
    J0 --> LoopI2(for i = 2 to len2)
    LoopI2 --> While1(while j > 0 && S2_i != S2_j+1)
    While1 -- 匹配失败 --> Back1(j = next_j)
    Back1 --> While1
    While1 -- 匹配成功或 j=0 --> Check1{S2_i == S2_j+1 ?}
    Check1 -- Yes --> IncJ1(j++)
    IncJ1 --> AssignNext(next_i = j)
    Check1 -- No --> AssignNext
    AssignNext --> LoopI2
    end

    LoopI2 --> Match(进行 S1 和 S2 的匹配)

    subgraph "KMP 主匹配过程"
    Match --> J0_M(j = 0)
    J0_M --> LoopI1(for i = 1 to len1)
    LoopI1 --> While2(while j > 0 && S1_i != S2_j+1)
    While2 -- 失配 --> Back2(j = next_j)
    Back2 --> While2
    While2 -- 匹配或 j=0 --> Check2{S1_i == S2_j+1 ?}
    Check2 -- Yes --> IncJ2(j++)
    IncJ2 --> CheckFinish{j == len2 ?}
    Check2 -- No --> CheckFinish
    CheckFinish -- 匹配成功 --> OutputPos(输出 i-len2+1)
    OutputPos --> Back3(j = next_j)
    CheckFinish -- 未完 --> LoopI1
    Back3 --> LoopI1
    end

    LoopI1 --> OutputNext(遍历输出 next 数组)
    OutputNext --> End(结束)

五、 样例数据与格式说明

题目名称：【模板】KMP字符串匹配

输入格式： 第 1 行输入一个字符串 $S_1$。 第 2 行输入一个字符串 $S_2$。

输出格式： 若干行，每行包含一个整数，表示 $S_2$ 在 $S_1$ 中出现的所有位置（按从小到大排序）。 最后一行输出 $|S_2|$ 个整数，表示 $S_2$ 的 $next$ 数组元素，用空格隔开。

样例输入 #1:

ABABABC
ABA

样例输出 #1:

1
3
0 0 1

数据规模与约定:

• 对于 $20\%$ 的数据：$|S_1| \le 10^3, |S_2| \le 10^2$。
• 对于 $100\%$ 的数据：$|S_1| \le 10^6, |S_2| \le 10^6$。
• 字符串仅包含英文大写字母。

六、 读题关键词与坑点总结

1. 关键词：所有出现位置
   • 这意味着找到一个匹配后，不能直接停止，而要利用 $next$ 数组“模拟失配”，寻找下一个重叠的匹配。
2. 关键词：1-indexed (下标从1开始)
   • NOI 题目通常习惯从 1 开始描述位置。在写代码时，你可以选择使用 std::string（0位开始）但输出结果加 1，或者开大数组从 s[1] 开始读入。
3. 关键词：最长公共前后缀 (Border)
   • 本题要求的 $next$ 数组定义是：$S_2$ 前 $i$ 个字符组成的子串中，最长的真前缀同时也是真后缀的长度。
4. 易错点：
   • next[1] 永远是 0。
   • 在主匹配过程中，当 j == len2 时，记录完答案后，要执行 j = next[j] 以便继续寻找下一个可能重叠的匹配（例如 AAAAA 中找 AAA）。

希望这些提示能帮你顺利通过此题！加油，少年。