P3375 【Template】KMP

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'$.

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

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$.

### 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