题目大意：两个字符串a和b，请将b在a中出现的所有位置输出来，并输出next数组。
题目描述
如题，给出两个字符串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<=1000
解题思路
1、前缀：以首字符开头的连续的字符，不包括自己，如abcd的前缀有a、ab、abc。
2、后缀：后末字符结尾的连续的字符，不包括自己，如abcd的后缀有d、cd、bcd。
3、next数组：next[i]表示0到i的字符串的最长公共前后缀的长度。
4、在匹配失败时，如果存在公共前后缀，则这部分字符不需要再比较了。
5、next数组代码解释：j是b串当前字符，i是公共前后缀的下一个字符。如果a[i]==b[j]，那么公共前后缀长度多1，也即i+1；如果不相同，则找公共前后缀长度小一些的，即看一下第c[i-1]个字符是否跟b[j]相同。例子：abadabab，在计算最后一个字符的next值时，i=3，j=7，c[i-1]=1……
6、KMP代码解释：i是a串当前字符，j是b串当前字符，如果两个字符相同，则继续比较后一位；否则，看一下是否有公共前后缀，有的话直接比较公共前后缀的下一个字符。
程序实现
