【题意】

给出模版串 $S$ 和子串 $s$。

要求在线性时间内，对于每个 $i \ (1 \le i \le S.{lenth} )$，求出 $S_i \dots S_{S.{lenth}}$ 与 $s$ 的最长公共前缀长度。

【输入格式】

第一行输入 $S$ 字符串。

第二行输入 $s$ 字符串。

两个字符串的长度小于等于10^6。

【输出格式】

输出 $S.lenth$个数，表示$S_i \dots S_{S_lenth}$ 与 $s$ 的最长公共前缀长度。

【样例输入】

aabbabaaab
aabb

【样例输出】

4 1 0 0 1 0 2 3 1 0