一、题目背景：P3375 【模板】KMP

这道题是 洛谷模板题，也是 KMP 算法的标准入门题。

题目核心要求

给定两个字符串 s1（文本串，长度为 n）和 s2（模式串，长度为 m），请完成两个任务：

1. 匹配任务：找出 s2 在 s1 中所有出现的位置（位置从 1 开始计数）。
2. 前缀函数任务：输出模式串 s2 每个前缀的 最长 Border 长度（即 KMP 的 Next 数组）。

输入输出样例

输入：

ABABABC
ABA

输出：

1
3
0 0 1

---

二、为什么要用 KMP？（从暴力匹配说起）

如果你写暴力匹配（双重循环），时间复杂度是 O(n×m)。当数据量达到 105 级别时，暴力匹配直接 TLE（超时）。

暴力匹配的致命缺陷

比如 s1 = "AAAAABAAAAA"，s2 = "AAAAA"：

• 当匹配到第 5 个字符时，B vs A 失配。
• 暴力做法：文本串指针 i 回退到 1，模式串指针 j 回退到 0，从头开始比。
• 问题：大量重复的比较操作被执行了，浪费了宝贵的运行时间。

KMP 的核心思想

利用模式串本身的对称性，在失配时不回退文本串指针 i，只回退模式串指针 j。这使得时间复杂度降为 O(n+m)，线性时间解决匹配问题。

---

三、核心概念：什么是 Next 数组？

KMP 的关键在于 Next 数组（也叫前缀函数）。

1. 定义

对于字符串 s 的前缀 s[0...i]，Next[i] 表示：

该前缀的 最长真 Border 长度。

2. 什么是 Border？

• Border：一个字符串的 非空真子串，满足 既是前缀又是后缀。
• 比如 "ABAB"：
  • 前缀 "AB" 既是前缀又是后缀 → 是 Border。
  • 前缀 "ABA" 不是 → 不等于后缀。
  • 所以 "ABAB" 的最长 Border 是 "AB"，长度为 2。

3. Next 数组的作用

当匹配失败时：

• 文本串 i 不动。
• 模式串 j 直接跳转到 Next[j-1] 的位置。原因：Next[j-1] 记录了当前最长的公共前后缀，我们只需要从这个位置继续匹配，不用重复比较已经匹配过的字符。

---

四、算法详解：Next 数组 & 匹配过程

1. Next 数组求解算法（前缀函数）

时间复杂度：O(m)核心逻辑：

• 初始化 Next[0] = 0（单个字符没有真子串）。
• 对于 i 从 1 到 m−1：
  • 令 j=Next[i−1]（继承前一位的最长公共前后缀长度）。
  • 失配回溯：只要 j>0 且 s[i]=s[j]，就令 j=Next[j−1]。
  • 匹配成功：如果 s[i]==s[j]，则 j++。
  • 令 Next[i] = j。

代码实现

vector<int> get_next(const string& s) {
    int m = s.size();
    vector<int> Next(m, 0); // Next数组初始化
    
    for (int i = 1; i < m; ++i) {
        int j = Next[i - 1]; // 关键：利用之前的信息
        
        // 失配时不断回溯
        while (j > 0 && s[i] != s[j]) {
            j = Next[j - 1];
        }
        
        // 匹配成功，长度加1
        if (s[i] == s[j]) {
            j++;
        }
        
        Next[i] = j;
    }
    return Next;
}

2. KMP 匹配过程

时间复杂度：O(n)核心逻辑：

• 定义双指针 i（遍历文本串）和 j（遍历模式串）。
• 遍历文本串：
  • 失配回溯：如果 j>0 且字符不相等，令 j=Next[j−1]。
  • 匹配成功：如果字符相等，令 j++。
  • 完全匹配：当 j==m 时，说明找到一个匹配位置。计算位置并记录，然后令 j=Next[j−1]（为了寻找重叠匹配）。

代码实现

vector<int> kmp_match(const string& s1, const string& s2, const vector<int>& Next) {
    int n = s1.size(), m = s2.size();
    vector<int> res; // 存储匹配位置
    int j = 0; // 模式串指针
    
    for (int i = 0; i < n; ++i) {
        // 失配回溯
        while (j > 0 && s1[i] != s2[j]) {
            j = Next[j - 1];
        }
        
        // 匹配成功
        if (s1[i] == s2[j]) {
            j++;
        }
        
        // 找到完整匹配
        if (j == m) {
            // 位置转换：0-based 转 1-based
            res.push_back(i - m + 2); 
            // 继续寻找下一个匹配
            j = Next[j - 1];
        }
    }
    return res;
}

---

五、完整 AC 代码

包含了输入输出、Next 数组计算、KMP 匹配，复制即可 AC。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 1. 计算Next数组（前缀函数）
vector<int> get_next(const string& s) {
    int m = s.size();
    vector<int> Next(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = Next[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = Next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        Next[i] = j;
    }
    return Next;
}

// 2. KMP匹配逻辑
vector<int> kmp(const string& s1, const string& s2, const vector<int>& Next) {
    int n = s1.size(), m = s2.size();
    vector<int> pos;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s1[i] != s2[j]) {
            j = Next[j - 1];
        }
        if (s1[i] == s2[j]) {
            j++;
        }
        if (j == m) {
            pos.push_back(i - m + 2); // 转换为1-based下标
            j = Next[j - 1];         // 继续匹配下一个
        }
    }
    return pos;
}

int main() {
    // 加速IO，竞赛必备
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    vector<int> Next = get_next(s2);
    vector<int> positions = kmp(s1, s2, Next);

    // 输出所有匹配位置
    for (int p : positions) {
        cout << p << '\n';
    }

    // 输出Next数组（题目要求）
    for (int i = 0; i < s2.size(); ++i) {
        cout << Next[i] << " \n"[i == s2.size() - 1];
    }

    return 0;
}

---

六、避坑指南（新手必看）

1. 数据类型溢出：
   • 虽然 106 以内可以用 int，但在竞赛中，字符串长度和索引建议直接使用 int。
   • 核心变量 i,j 必须是整型。
2. 位置转换：
   • 题目要求从 1 开始输出位置。
   • 代码中 i - m + 2 是 0-based 转 1-based 的关键公式。
   • 如果直接输出 i - m + 1，会少 1，导致 WA。
3. Next 数组初始化：
   • Next[0] 必须是 0，不能留垃圾值。
4. 失配条件：
   • 必须写 while (j > 0 && ...)，保证 j 不会越界变成 -1。

---

七、总结

KMP 算法是字符串匹配的 基石。

• 核心：利用 前缀函数（Next 数组） 记录模式串的对称性。
• 复杂度：O(n+m)，秒杀暴力。
• 适用场景：所有单模式串匹配问题，如查找关键词、统计出现次数、AC 自动机的基础。