2419. KMP算法【模板】
1000ms
256MB
简单
字符串
模板题
题目描述
给定两个字符串：
- 文本串 $s_1$
- 模式串 $s_2$
若 $s_1$ 的某个子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现。
请：
1. 输出 $s_2$ 在 $s_1$ 中所有出现的位置；
2. 输出模式串每个前缀的最长 border 长度。
输入格式
- 第一行：字符串 $s_1$
- 第二行：字符串 $s_2$
输出格式
- 先输出若干行，每行一个整数，表示模式串出现的位置（从小到大）。
- 最后一行输出模式串每个前缀的最长 border 长度。
样例 1
输入 (Input)
输出 (Output)
- $1 \le |s_1|, |s_2| \le 10^6$
- 字符均为大写英文字母
本题需要使用：
- KMP 算法
- next（失败函数）数组
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功