【模板】KMP字符串匹配

题目描述

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

输入输出格式

输入格式


第一行为一个字符串,即为s1 第二行为一个字符串,即为s2

输出格式


若干行,每行包含一个整数,表示s2在s1中出现的位置 接下来1行,包括length(s2)个整数,表示前缀数组next[i]的值。

输入输出样例

输入样例 #1

ABABABC
ABA

输出样例 #1

1
3
0 0 1 

说明

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