【模板】KMP字符串匹配

题目描述

如题,给出两个字符串 $s_1$ 和 $s_2$,其中 $s_2$ 为 $s_1$ 的子串,求出 $s_2$ 在 $s_1$ 中所有出现的位置。 **为了减少骗分的情况,接下来还要输出子串的前缀数组 next。** (如果你不知道这是什么意思也不要问,去百度搜 `kmp算法` 学习一下就知道了。)

输入输出格式

输入格式


第一行为一个字符串,即为 $s_1$。 第二行为一个字符串,即为 $s_2$。

输出格式


若干行,每行包含一个整数,表示 $s_2$ 在 $s_1$ 中出现的位置 接下来 $1$ 行,包括 $|s2|$ 个整数,表示前缀数组 $next_i$ 的值。

输入输出样例

输入样例 #1

ABABABC
ABA

输出样例 #1

1
3
0 0 1 

说明

时空限制:1000ms,128M 数据规模: 设 $s_1$ 长度为 $N$,$s_2$ 长度为 $M$。 对于 $30\%$ 的数据:$N\leq 15$, $M\leq 5$。 对于 $70\%$ 的数据:$N\leq 10000$, $M\leq 100$。 对于 $100\%$ 的数据:$N\leq 1000000$, $M\leq 1000000$。 样例说明: ![](https://cdn.luogu.com.cn/upload/pic/2257.png) 所以两个匹配位置为 $1$ 和 $3$,输出 $1$, $3$