문자열학

문자열 $u = u_1 \dots u_n$에 대해 $\mathrm{pre}(u, i)$는 접두사 $u_1 \dots u_i$를 나타낸다. 같은 방식으로 $\mathrm{suf}(u, i)$는 접미사 $u_{n-i+1} \dots u_n$을 나타낸다. $\mathrm{pre}(u, 0)$과 $\mathrm{suf}(u, 0)$은 모두 빈 문자열이다.

두 문자열 $u = u_1 \dots u_n$과 $v = v_1 \dots v_m$에 대해 $u + v$는 $u_1 \dots u_n v_1 \dots v_m$을 이어 붙인 문자열이다. 또한

$\mathrm{presuf}(u, v) = \max\{i \mid i < n \text{ and } i \leq m \text{ and } \mathrm{pre}(u, i) = \mathrm{suf}(v, i)\}$

문자열 $s = s_1 \dots s_n$과 $t = t_1 \dots t_m$이 주어진다. $f(i) = \mathrm{presuf}(s, \mathrm{pre}(s, i) + t)$라 할 때, $f(0), \dots, f(n-1)$의 값을 구하라.

입력은 여러 테스트 케이스로 이루어지며 파일 끝에서 끝난다. 각 테스트 케이스는 두 줄로 되어 있다. 첫 줄에는 문자열 $s_1 \dots s_n$이, 둘째 줄에는 문자열 $t_1 \dots t_m$이 주어진다.

각 테스트 케이스마다 $f(0), \dots, f(n-1)$을 나타내는 정수 $n$개를 출력한다.

$1 \leq n, m \leq 10^6$이다. 모든 $s_i$와 $t_i$는 a부터 z까지의 소문자다. 한 입력에서 $\max(n, m)$의 합은 $10^6$을 넘지 않는다.

두 번째 케이스에서 $f(4) = \mathrm{presuf}(\mathtt{ababa}, \mathtt{abab} + \mathtt{a}) = \mathrm{presuf}(\mathtt{ababa}, \mathtt{ababa})$이다.

따라서 $f(4) = 3$이다.