← 返回题目列表

Codeforces · 1137/B

B. 营地时间表

中文机器翻译题面 查看原题

全国知名的春季编程营新一期即将开营。于是,所有友好的策展人和老师团队开始制定夏令营的日程。经过不断的讨论,他们提出了一个时间表$$$s$$$,它可以表示为一个二进制字符串,其中如果学生将在第$$$i$$$日进行比赛,则第$$$i$$$个符号为“1”,如果他们休息一天,则为“0”。

在最后一刻,Gleb 说,如果按照时间表 $$$t$$$ 运行(可以用​​与时间表 $$$s$$$ 相同的格式描述),营地将是最有生产力的。由于当前的天数可能与时间表 $$$t$$$ 中的天数不同,Gleb 要求必须更改营地的时间表,以便 $$$t$$$ 作为子串在其中出现的次数尽可能多。同时,比赛日和休息日的数量不应改变,只是其顺序可以改变。

你能以最好的方式重新安排日程吗?

输入

第一行包含字符串 $$$s$$$ ($$$1 \leqslant |s| \leqslant 500\,000$$$),表示营地日程表的当前项目。

第二行包含字符串 $$$t$$$ ($$$1 \leqslant |t| \leqslant 500\,000$$$),表示根据 Gleb 的最佳调度。

字符串 $$$s$$$ 和 $$$t$$$ 仅包含字符“0”和“1”。

输出

在唯一一行中打印子字符串数量最多等于 $$$t$$$ 的时间表。打印的时间表应仅包含字符“0”和“1”,并且零的数量应等于 $$$s$$$ 中零的数量,而 1 的数量应等于 $$$s$$$ 中 1 的数量。

如果有多个最佳时间表,请打印其中任何一个。

示例

输入 #1

101101
110

输出 #1

110110

输入 #2

10010110
100011

输出 #2

01100011

输入 #3

10
11100

输出 #3

01

注意

在第一个示例中出现两次,一次从第一个位置开始,一次从第四个位置开始。

在第二个示例中,仅出现一次,从第三个位置开始。请注意,答案不是唯一的。例如,如果我们将第一天(休息日)移至最后一个位置,$$$t$$$ 出现的次数不会改变。

在第三个示例中,甚至不可能出现一次。