企业官网建设流程全解析

洛谷P3375，字符串入门绕不过去的一道题。题目名字就叫 KMP，要求你把模式串在文本串里的所有出现位置全部找出来，再输出模式串的 next 数组。看起来只是模板题，但里面涉及的前缀函数、失配跳转、1-based 下标习惯，足够让新手琢磨好几天。这篇文章我会从题目本身讲起，手算一遍 next，给出一份可以直接 AC 的代码，再聊聊那些让你只拿 80 分的坑。

如果你刚开始刷洛谷字符串题单，或者已经背过 KMP 模板但一到变形题就懵，那这篇很适合你。我会尽量用“搞懂为什么”的方式讲，而不是让你死记代码。看完之后，你不仅能过 P3375，还能顺手摸清最小循环节、KMP 自动机这些后续知识。

1. 题目说了什么：先读懂P3375再动手

1.1 题目输入输出长什么样

P3375 的题目非常直白：输入两行字符串，第一行是文本串 s1，第二行是模式串 s2。要求输出 s2 在 s1 中出现的所有起始位置，紧接着输出一行 next 数组。这里有两个容易被新手忽略的细节：位置从 1 开始计数，而不是从 0 开始；next 数组输出的是模式串每个位置对应的失配跳转值，也就是通常说的“前缀函数”。

比如样例输入是：

ABABAC ABA

正确输出是：

1 3 0 0 1

第一行表示模式串 ABA 在文本串 ABABAC 里出现了两次，起始位置分别是第 1 个字符和第 3 个字符。第二行是模式串 ABA 的 next 数组。很多第一次写的人会把位置输出成 0 和 2，因为习惯了数组下标从 0 开始，结果白交几发才知道要对输出位置加 1。

1.2 KMP 算法在解决哪类问题

字符串匹配是个很基础的问题：给你一个文本串和一个模式串，问模式串在文本串里出现了几次、分别在哪些位置。最简单的暴力做法是从文本串的每个位置开始，逐个字符和模式串比较，一旦不匹配就放弃当前位置，从下一个位置重新开始。这种做法的复杂度是 O(n×m)，n 和 m 分别代表两个串的长度。当两个串都到 10^6 级别，暴力基本就卡死了。

KMP 算法的厉害之处在于把匹配复杂度降到 O(n+m)。它靠的不是什么黑魔法，而是提前对模式串做预处理，生成 next 数组，然后在匹配过程中让文本串的下标一直往前走，不回头。文本串每个字符最多被比较一次，模式串下标偶尔会回退，但回退的次数有上限，所以总复杂度是线性的。这个“文本串不回退”的特性，是理解 KMP 的关键。

1.3 一个“为什么用 KMP”的直觉

打个比方：你在读一页纸，要找某个词出现的位置。暴力做法是每到一个字就从头对一遍，一旦发现不对就挪一格再从头对，前面已经看过几百遍的字还得反复看。KMP 的做法是，你在纸上记了个小抄：最近这一段我已经匹配到了模式串的第几个字符，如果下一个字不对，我该跳到哪里继续对，而不是重新翻回开头。

具体到模式串“ABA”，如果你已经匹配到了“AB”，发现主串下一个字符不是 A，暴力做法会把模式串整体右移一位，重新从 A 开始比。但 KMP 知道“AB”这个前缀里，最长相等前后缀是 0，于是直接让模式串回到开头，主串还是一路往后扫。这样主串只扫一遍，模式串的移动也有规律。这个“小抄”就是 next 数组。

2. next 数组：KMP 的灵魂与手算方法

2.1 next 数组到底存的是什么

网上关于 next 数组的讲法五花八门，有人说是“失配后跳转的位置”，有人说是“最长相等前后缀长度”，这两种说法其实是一回事，只要你定义好下标。洛谷 P3375 里要输出的 next，通常表示：对于模式串的前 i 个字符，它们组成的子串中，最长相等的前缀和后缀的长度。注意，前缀不能是整个子串本身，后缀也不能是整个子串本身。

拿模式串“ABA”来说：

• 前 1 个字符“A”：没有真前缀和真后缀，所以 next[1] = 0。
• 前 2 个字符“AB”：前缀“A”，后缀“B”，不相等，所以 next[2] = 0。
• 前 3 个字符“ABA”：前缀有 A、AB，后缀有 A、BA，能相等且最长的就是“A”，长度 1，所以 next[3] = 1。

这就是样例输出的第二行：0 0 1。理解了这个定义，手算 next 就只是细心问题。

2.2 手算 next 的完整过程

我们换一个更典型的模式串“ABABACA”来手算。先把每个前缀写出来：

• i=1，子串“A”，next[1]=0。
• i=2，子串“AB”，前缀 A，后缀 B，不等，next[2]=0。
• i=3，子串“ABA”，最长相等前后缀是“A”，长度 1，next[3]=1。
• i=4，子串“ABAB”，最长相等前后缀是“AB”，长度 2，next[4]=2。
• i=5，子串“ABABA”，最长相等前后缀是“ABA”，长度 3，next[5]=3。
• i=6，子串“ABABAC”，从头找后缀，只有 C 开头的后缀“C”“AC”“BAC”“ABAC”“BABAC”能和前缀对上吗？对比后没有一个相等，next[6]=0。
• i=7，子串“ABABACA”，最后是 A，和开头 A 相等，再长一点的“AB”和高尾“CA”不相等，所以 next[7]=1。

最终手算结果就是：

这个表你可以对照着后面代码一步步走，会很有帮助。

2.3 next 数组的编程递推逻辑

编程生成 next 数组，不能真的每个 i 都重新把前缀后缀比一遍，那样又变成 O(m²) 了。KMP 的作者想到的办法是：利用已经算出来的 next[i-1]，快速往后扩展。

核心逻辑很像动态规划。假设我们处理到模式串第 i 位，用变量 j 表示当前已经匹配好的前缀长度，也就是想让 b[i] 和 b[j+1] 去比较。如果两个字符相等，说明最长相等前后缀可以变成 j+1；如果不相等，就把 j 退回到 next[j]，再继续尝试。这个 while 循环是 KMP 程序里最容易绕晕的地方，但只要你明确“j 是当前已匹配长度，next[j] 是前 j 个字符的最长相等前后缀长度”，就能看懂。

3. 完整代码与洛谷 AC 实践

3.1 一份能 AC 的 C++ 模板

下面是我在洛谷 P3375 上常用的写法，使用 1-based 下标和 C 风格字符串。代码直观，适合理解：

#include <bits/stdc++.h> using namespace std; const int N = 1000005; char a[N], b[N]; int nxt[N]; int main() { cin >> a + 1 >> b + 1; int n = strlen(a + 1); int m = strlen(b + 1); // 求模式串 b 的 next 数组 for (int i = 2, j = 0; i <= m; ++i) { while (j && b[i] != b[j + 1]) j = nxt[j]; if (b[i] == b[j + 1]) ++j; nxt[i] = j; } // 用 next 数组去匹配主串 a for (int i = 1, j = 0; i <= n; ++i) { while (j && a[i] != b[j + 1]) j = nxt[j]; if (a[i] == b[j + 1]) ++j; if (j == m) { cout << i - m + 1 << '\n'; j = nxt[j]; } } // 输出 next 数组 for (int i = 1; i <= m; ++i) { cout << nxt[i] << ' '; } return 0; }

这段代码在题目范围内能稳定运行。nxt[i] 表示前 i 个字符的最长相等前后缀长度，同时也能直接作为失配后模式串下标回退的目标位置。两个循环都是线性的，整体复杂度 O(n+m)。

3.2 下标规范：从 1 开始还是从 0 开始

很多新手困惑：为什么代码里用 a+1 和 b+1？因为 C 风格 char 数组从 0 下标开始，cin >> a + 1 让字符串从下标 1 开始存，这样模式串第 1 个字符就是 b[1]，和题目的“位置从 1 开始”天然对齐。匹配成功时 i - m + 1 就是模式串在主串里的起始位置。

如果你更习惯 C++ 的 string 和 0-based 下标，也可以写出前缀函数版本：

vector<int> prefix_function(const string& s) { int m = s.size(); vector<int> pi(m, 0); for (int i = 1; i < m; ++i) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) ++j; pi[i] = j; } return pi; }

两种思路都对，但千万别混着用。最常见的问题就是 1-based 的 next 数组和 0-based 的匹配代码揉在一起，结果小样例碰巧对，大数据全错。我的建议是：如果打竞赛，选一种记牢，比赛时不纠结。

3.3 边界与常见错误

数组大小是第一个坑。洛谷的字符串长度可以到 10^6，如果开char a[100000]，肯定越界。我习惯直接开const int N = 1000005，而且用全局数组，避免爆栈。

边界情况也要仔细想。比如模式串长度为 1 时，匹配逻辑里 j 永远只在 0 和 1 之间变化；每次匹配成功后 j = nxt[j]，而 nxt[1] = 0，所以不会出问题。要是模式串只有一个字符且主串里全是这个字符，代码会输出每一个出现位置，这正是题目要求的。

输出格式也要注意。洛谷对行末空格一般不强求，但为了保险，我会在 next 数组每个数后面输出空格，这就和样例格式一致。有人在每个位置后面加了换行，结果格式错被 WA，这种错误最冤枉。

3.4 本地测试与“80分”排查

我见过不少朋友本地随便测都通过，一提交就只拿 80 分，字符串题尤其容易这样。先说“洛谷该怎么放数据”这个经典问题：本地测试根本不需要建数据文件，直接把样例复制粘贴到终端标准输入就行。如果你非要用文件，可以在 main 里写freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);，然后把 in.txt 放在源文件同目录下。但提交前千万记得把这两行注释掉，否则 OJ 上读不到 in.txt，结果必然出错。

至于 80 分，我总结过几个高发原因：一是数组开小了，小数据越界看不出，大数据直接段错误；二是 next 数组计算错位，比如用 0-based 逻辑写成j = nxt[j - 1]，但下标却按 1-based 用；三是匹配成功后忘了更新j = nxt[j]，导致下一次匹配从错误位置继续。你遇到 80 分，优先检查这三处。

4. 从模板题走向进阶应用

4.1 用 next 数组找最小循环节

P3375 只是让输出 next，但 next 数组最经典的延伸用途是找字符串的最小循环节。对于一个长度为 m 的字符串，如果它的 next[m] 不为 0，且 m 能被 m - next[m] 整除，那么这个字符串是由长度为 m - next[m] 的子串重复构成的。

举个例子，字符串“ABCABCABC”，长度 9，next[9] = 6，因为前 6 个字符“ABCABC”和后 6 个字符“ABCABC”完全一致。m - next[9] = 3，9 能被 3 整除，说明最小循环节是“ABC”。这种结论在解决周期性问题时非常有用，比如判断一个字符串能否由某个子串重复拼接而成。

4.2 由单模式匹配扩展到多模式匹配

KMP 是单模式串匹配算法，但它的思想可以扩展到多个模式串。你在洛谷刷题时会遇到 AC 自动机，它本质上是 Trie 树加失败指针，而失败指针的构造思想和 KMP 的 next 数组几乎一模一样。把 KMP 吃透了，学 AC 自动机时你会发现很多概念只是换了个皮。

如果模式串有很多个，比如几千个，一个个跑 KMP 复杂度会比较高，这时才会用到 AC 自动机。所以别急着跳级，先把 P3375 的单模式匹配写到滚瓜烂熟，再去看多模式匹配，路径会平顺很多。

4.3 刷题顺序与后续建议

洛谷的字符串题单里，P3375 是很好的起点。刷完它，我建议你马上找几道综合题练手，比如 P3193 这类把 KMP 和 DP 结合的题。这类题看着吓人，但最底层的匹配逻辑仍然靠 next 数组。

做题时不要只抄模板，而要在心里过一遍完整流程：模式串第几位失配，j 应该跳到哪里，为什么跳过去之后不会漏掉答案。等你把每一个 while 循环都能讲明白，KMP 才算真正熟练。再往后你可以刷一些涉及字符串哈希、Manacher、后缀数组的题，但有了 KMP 打底，理解这些算法会轻松很多。

5. 我的一点个人体会

KMP 难不在代码量，而在于“失配之后到底该怎么利用已经匹配的信息”。我记得第一次手算 next 数组时，对着表反反复复查了好几次，才真正明白为什么匹配失败后不是从头开始，而是跳到最长相等前后缀的后面。后来我给周围人讲这道题，总会让他们先拿纸笔走一遍样例，效果比直接看十篇博客都好。

最后分享一个我自己的小习惯：学字符串算法时，在草稿纸上用两个下标分别标记主串位置和模式串位置，每一步失配就在模式串上方画一个箭头，指向 next 数组告诉你要跳的位置。多走几轮，你会觉得 KMP 并不是什么玄学，而是一种特别优雅的“记忆化”手法。希望这篇能帮你顺利拿下 P3375，少踩几个我当年踩过的坑。