该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。为了减少骗分的情况，接下来还要输出子串的前缀数组next。

数据规模：

设s1长度为N，s2长度为M

$N<=10^6，M<=10^6$

Input Format

第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

Output Format

若干行，每行包含一个整数，表示s2在s1中出现的位置

接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。

ABABABC
ABA​

1
3
0 0 1​

Source

串 KMP