【题目来源】
洛谷：P3375 【模板】KMP - 洛谷
【题目描述】
给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l,r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。
现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
定义一个字符串 \(s\) 的 border 为 \(s\) 的一个非 \(s\) 本身的子串 \(t\)，满足 \(t\) 既是 \(s\) 的前缀，又是 \(s\) 的后缀。
对于 \(s_2\)，你还需要求出对于其每个前缀 \(s′\) 的最长 border \(t′\) 的长度。
【输入】
第一行为一个字符串，即为 \(s_1\)。
第二行为一个字符串，即为 \(s_2\)。
【输出】
首先输出若干行，每行一个整数，按从小到大的顺序输出 \(s_2\) 在 \(s_1\) 中出现的位置。
最后一行输出 \(∣s_2∣\) 个整数，第 \(i\) 个整数表示 \(s_2\) 的长度为 \(i\) 的前缀的最长 border 长度。
【输入样例】
ABABABC
ABA
【输出样例】
1
3
0 0 1
【解题思路】
【算法标签】
《洛谷 P3375 KMP》 #字符串# #KMP# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义最大字符串长度char s[N], p[N]; // s: 主串, p: 模式串
int nex[N]; // KMP算法中的next数组int main()
{// 输入主串和模式串（从下标1开始存储）cin >> s + 1;int n = strlen(s + 1); // 主串长度cin >> p + 1;int m = strlen(p + 1); // 模式串长度// 计算模式串的next数组nex[0] = nex[1] = 0; // 初始化前两个位置for (int i = 2, j = 0; i <= m; i++){// 当不匹配时回退while (j && p[i] != p[j + 1]){j = nex[j];}// 匹配成功则j增加if (p[i] == p[j + 1]){j++;}nex[i] = j; // 记录当前位置的next值}// 使用KMP算法进行模式匹配for (int i = 1, j = 0; i <= n; i++){// 当不匹配时利用next数组回退while (j && s[i] != p[j + 1]){j = nex[j];}// 匹配成功则j增加if (s[i] == p[j + 1]){j++;}// 完全匹配时输出起始位置if (j == m){cout << i - m + 1 << endl;}}// 输出next数组（调试用）for (int i = 1; i <= m; i++){cout << nex[i] << " ";}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义最大字符串长度int ne[N]; // KMP算法中的next数组
char p[N], s[N]; // p: 模式串, s: 主串（都从下标1开始存储）int main()
{// 输入主串和模式串（从下标1开始存储）cin >> s + 1;int m = strlen(s + 1); // 主串长度cin >> p + 1;int n = strlen(p + 1); // 模式串长度// 计算模式串的next数组for (int i = 2, j = 0; i <= n; i++){// 当不匹配时利用next数组回退while (j && p[i] != p[j + 1]){j = ne[j];}// 匹配成功则j增加if (p[i] == p[j + 1]){j++;}ne[i] = j; // 记录当前位置的next值}// KMP算法匹配过程for (int i = 1, j = 0; i <= m; i++){// 当不匹配时利用next数组回退while (j && s[i] != p[j + 1]){j = ne[j];}// 匹配成功则j增加if (s[i] == p[j + 1]){j++;}// 完全匹配时输出起始位置if (j == n){cout << i - n + 1 << endl;}}// 输出next数组（调试用）for (int i = 1; i <= n; i++){cout << ne[i] << " ";}return 0;
}
【运行结果】
ABABABC
ABA
1
3
0 0 1