题目描述

《KMP》

【KMP】 给出两个字符串 s1 和 s2，若 s1 的区间 [L,R] 子串与 s2 完全相同，则称 s2 在 s1中出现了，其出现位置为 L。现在请你求出 s2 在 s1 中所有出现的位置。s1 的区间位置L,R都从 1 开始。 定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。 对于 s2，你还需要求出对于其每个前缀 s′的最长 border t′的长度。

输入格式

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

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。 最后一行输出 s2 长度个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。

样例

输入样例 1

ABABABC
ABA

输出样例 1

1
3
0 0 1

输入样例 2

ABABABABA
ABA

输出样例 2

1
3
5
7
0 0 1

输入样例 3

AAAAAAAAAA
AAA

输出样例 3

1
2
3
4
5
6
7
8
0 1 2

输入样例 4

ABCDEFGHI
XYZ

输出样例 4

0 0 0