问题 J: 8.2.2.2 KMP字符串匹配
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：143
解决：175
题目描述
给定两个字符串s1和s2，若s1的[l,r]区间的子串与s2完全相同，则称s2在s1中出现了，其出现位置为l。请求出s2在s1中所有出现的位置。定义一个字符串s的border为s的一个非s本身的子串t，求满足t既是s的前缀，又是s的后缀。对于s2，还需要求出对于其每个前缀的最长border的长度。
输入
输入为2行，第1行为字符串s1，第2行为字符串s2。1<=|s1|,|s2|<=10e6，字符串只含大写英文字母。
输出
首先输出若干行，每行一个整数，按从小到大的顺序输出s2在s1中出现的位置。最后一行输出|s2|个整数，第i个整数表示s2的长度为i的前缀的最长border的长度。
样例输入 复制
ABABABC
ABA样例输出 复制
1
3
0 0 1