Description

Given two strings $s_1$ and $s_2$, if the substring of $s_1$ on the interval $[l, r]$ is exactly the same as $s_2$, then $s_2$ is said to occur in $s_1$, and its occurrence position is $l$.
Now please find all occurrence positions of $s_2$ in $s_1$.

Define the border of a string $s$ as a substring $t$ of $s$ that is not the whole $s$, and satisfies that $t$ is both a prefix and a suffix of $s$.
For $s_2$, you also need to compute, for each of its prefixes $s'$, the length of the longest border $t'$.

Input Format

The first line contains a string, which is $s_1$.
The second line contains a string, which is $s_2$.

Output Format

First output several lines, each with an integer, output the occurrence positions of $s_2$ in $s_1$ in increasing order.
The last line outputs $|s_2|$ integers, where the $i$-th integer denotes the length of the longest border of the prefix of $s_2$ with length $i$.

ABABABC
ABA

1
3
0 0 1 

Hint

Explanation for Sample 1

.

For the length-$3$ prefix ABA of $s_2$, the string A is both its suffix and its prefix, and it is the longest one, so the longest border length is $1$.

Constraints and Notes

This problem uses bundled test points, with 4 subtasks.

• Subtask 0 (30 points): $|s_1| \leq 15$, $|s_2| \leq 5$.
• Subtask 1 (40 points): $|s_1| \leq 10^4$, $|s_2| \leq 10^2$.
• Subtask 2 (30 points): No special constraints.
• Subtask 3 (0 points): Hack.

For all test points, it is guaranteed that $1 \leq |s_1|, |s_2| \leq 10^6$, and both $s_1$ and $s_2$ contain only uppercase English letters.

Translated by ChatGPT 5