题目描述

给出两个字符串s和p​，若s​的区间[l, r]子串与p​完全相同，则称p​在s中出现了，其出现位置为pos。
现在请你求出p​在s中所有出现的位置。

定义一个字符串s的 border 为s的一个非s本身的子串t，满足t既是s的前缀，又是s的后缀。
对于p​，你还需要求出对于其每个前缀s'的最长 border的长度。

输入格式

第一行为一个字符串，即为s。

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

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出p在s中出现的位置。

最后一行输出|p|个整数，第i个整数表示p​的长度为i的前缀的最长 border 长度。

数据范围：

对于全部的测试点，保证1≤∣s1​∣,∣s2​∣≤${10}^6$。

ABABABC
ABA

1
3
0 0 1