【 Description 】
给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next，next[j]=k 表示第j个字符跟母串不匹配的时候，需要让子串的第k个字符跟母串比，j从0开始，且next[0]=−1，next[1]=0。
【 Input 】
第一行为一个字符串，即为s1
第二行为一个字符串，即为s2
【 Output 】
若干行，每行包含一个整数，表示s2在s1中出现的位置
接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。
【HINT】
设s1长度为N，s2长度为M
对于30%的数据：N<=15，M<=5
对于70%的数据：N<=10000，M<=100
对于100%的数据：N<=1000000，M<=1000000
