← 返回题目列表

Codeforces · 332/E

E. 二进制密钥

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

假设p和q是正长度的字符串,分别称为容器和密钥,字符串q仅由字符0和1组成。让我们看一个从给定容器p中提取消息s的简单算法:

给定的伪代码中,i、j 为整型变量,s 为字符串,'=' 为赋值运算符,'==' 为比较操作,'[]' 为获取预设索引的字符串字符操作,'<>' 为空字符串。我们假设所有字符串中的字符都是从零开始编号的。

我们知道实现这种算法非常容易,因此您的任务会略有不同。您需要构造长度为 k 的字典顺序最小密钥,以便在使用它时,上面给出的算法从容器 p 中提取消息 s (否则会发现这样的密钥不存在)。

输入

输入的前两行是非空字符串 p 和 s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200),分别描述容器和消息。字符串可以包含 ASCII 代码从 32 到 126(含 32 和 126)的任何字符。

第三行包含一个整数 k (1 ≤ k ≤ 2000) — 密钥的长度。

输出

打印所需的密钥(长度为 k 的字符串,仅由字符 0 和 1 组成)。如果键不存在,则打印单个字符 0。

示例

输入 #1

abacaba
aba
6

输出 #1

100001

输入 #2

abacaba
aba
3

输出 #2

0

注意

字符串 x = x1x2... xp 按字典顺序小于字符串 y = y1y2... yq,如果 p < q 且 x1 = y1, x2 = y2, ... , xp = yp,或者存在这样的整数 r (0 ≤ r < min(p, q)) 使得 x1 = y1, x2 = y2, ... , xr = yr 并且xr + 1 < yr + 1。根据 ASCII 代码对符号进行比较。