Stringology

For a string $u = u_1 \dots u_n$, Bobo denotes the prefix $u_1 \dots u_i$ by $\mathrm{pre}(u, i)$. Similarly, he denotes the suffix $u_{n - i + 1} \dots u_n$ by $\mathrm{suf}(u, i)$. In particular, $\mathrm{pre}(u, 0)$ and $\mathrm{suf}(u, 0)$ are empty strings.

For two strings $u = u_1 \dots u_n$ and $v = v_1 \dots v_m$, Bobo denotes the concatenation $u_1 \dots u_n v_1 \dots v_m$ by $u + v$. Also, $$\mathrm{presuf}(u, v) = \max\{i \mid i < n \text{ and } i \leq m \text{ and } \mathrm{pre}(u, i) = \mathrm{suf}(v, i) \}\text{.}$$

Given two strings $s = s_1 \dots s_n$ and $t = t_1 \dots t_m$, let $f(i) = \mathrm{presuf}(s, \mathrm{pre}(s, i) + t)$. Find the value of $f(0), \dots, f(n - 1)$.

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains a string $s_1 \dots s_n$.

The second line contains a string $t_1 \dots t_m$.

For each test case, output $n$ integers which denote $f(0), \dots, f(n - 1)$.

• $1 \leq n, m \leq 10^6$
• $s_i \in \{a, \dots, z\}$ for each $1 \leq i \leq n$
• $t_i \in \{a, \dots, z\}$ for each $1 \leq i \leq m$
• In each input, the sum of $\max(n, m)$ $\leq 10^6$.

For the second case, $f(4) = \mathrm{presuf}(s, \mathrm{pre}(s, 4) + t) = \mathrm{presuf}($ababa$, $abab$ + $a$) = \mathrm{presuf}($ababa$, $ababa$)$.

Therefore, $f(4) = 3$.