【题目来源】
AcWing：831. KMP字符串 - AcWing题库
【题目描述】
给定一个字符串 \(S\)，以及一个模式串 \(P\)，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 \(P\) 在字符串 \(S\) 中多次作为子串出现。
求出模式串 \(P\) 在字符串 \(S\) 中所有出现的位置的起始下标。
【输入】
第一行输入整数 \(N\)，表示字符串 \(P\) 的长度。
第二行输入字符串 \(P\)。
第三行输入整数 \(M\)，表示字符串 \(S\) 的长度。
第四行输入字符串 \(S\)。
【输出】
共一行，输出所有出现位置的起始下标（下标从 \(0\) 开始计数），整数之间用空格隔开。
【输入样例】
3
aba
5
ababa
【输出样例】
0 2
【解题思路】
【算法标签】
《AcWing 831 KMP字符串》 #KMP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010, M = 1000010; // 定义常量N和M，分别表示模式串和文本串的最大长度
int n, m; // n: 模式串长度，m: 文本串长度
char p[N], s[M]; // p: 模式串，s: 文本串
int ne[N]; // ne: next数组，用于KMP算法int main() {cin >> n >> p + 1 >> m >> s + 1; // 输入模式串和文本串（从下标1开始存储）// KMP算法预处理next数组for (int i = 2, j = 0; i <= n; i++) {while (j && p[i] != p[j + 1]) j = ne[j]; // 不匹配时回退if (p[i] == p[j + 1]) j++; // 匹配时j前进ne[i] = j; // 更新next数组}// KMP匹配过程for (int i = 1, j = 0; i <= m; i++) {while (j && s[i] != p[j + 1]) j = ne[j]; // 不匹配时回退if (s[i] == p[j + 1]) j++; // 匹配时j前进if (j == n) { // 完全匹配printf("%d ", i - n); // 输出匹配的起始位置j = ne[j]; // 回退，继续匹配}}return 0;
}
【运行结果】
3
aba
5
ababa
0 2