Stringology

For a string $u = u_1 \dots u_n$, $\mathrm{pre}(u, i)$ denotes the prefix $u_1 \dots u_i$. Likewise, $\mathrm{suf}(u, i)$ denotes the suffix $u_{n-i+1} \dots u_n$. Both $\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$, $u + v$ denotes the concatenation $u_1 \dots u_n v_1 \dots v_m$. 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)\}$

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 $f(0), \dots, f(n-1)$.

The input consists of several test cases, ending at end-of-file. Each test case has two lines. The first line contains the string $s_1 \dots s_n$, and the second line contains the string $t_1 \dots t_m$.

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

$1 \leq n, m \leq 10^6$. Each $s_i$ and $t_i$ is a lowercase letter from a to z. In each input, the sum of $\max(n, m)$ is at most $10^6$.

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

So $f(4) = 3$.