题目
洛谷 P3375（【模板】KMP）：给出文本串 s₁ 和模式串 s₂，输出 s₂ 在 s₁ 中所有出现位置，并输出 s₂ 每个前缀的最长 border（既是前缀又是后缀的真子串）长度——即 KMP 的 next/LPS 数组。
KMP 算法回顾
KMP（Knuth-Morris-Pratt）在匹配失败时利用已比较的信息，让模式串”跳着走”，避免主串指针回溯，最坏复杂度 O(n + m)。核心是 LPS 数组（最长相同前后缀长度）：
- 构建 LPS：
lps[i]表示模式串前 i+1 个字符的最长相同前后缀长度。指针 i 遍历，j 记录当前匹配长度；s[i]==s[j]则lps[i]=j+1，否则回退j = lps[j-1]； - 匹配：主串指针 i 不回退，模式串指针 j 按 LPS 跳转；j 到末尾即找到一个匹配位置，然后
j = lps[j-1]继续找下一个。
AC 代码（C++17）
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
cin >> s1 >> s2;
int m = s2.size();
// 1. 构建 LPS
vector<int> lps(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && s2[i] != s2[j]) j = lps[j - 1];
if (s2[i] == s2[j]) j++;
lps[i] = j;
}
// 2. 匹配
vector<int> pos;
for (int i = 0, j = 0; i < (int)s1.size(); i++) {
while (j > 0 && s1[i] != s2[j]) j = lps[j - 1];
if (s1[i] == s2[j]) j++;
if (j == m) {
pos.push_back(i - m + 2); // 1-based 位置
j = lps[j - 1]; // 继续找下一个
}
}
for (int p : pos) cout << p << "n";
for (int i = 0; i < m; i++) cout << lps[i] << (i + 1 == m ? "n" : " ");
return 0;
}
要点
- 匹配位置的下标转换：KMP 匹配结束时
i指向模式串末尾，起点（1-based）为i - m + 2，写错是常见 WA 点； - 找到匹配后继续找：必须
j = lps[j-1]而不是j = 0，否则会漏掉重叠出现的模式串； - LPS 输出格式：题目要求空格分隔、最后一个无多余空格（或直接换行）。
