← 返回题目列表

AtCoder · abc370_c

E. 字梯

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

分数: 300 点

问题陈述

给你两个字符串 S 和 T 由小写英文字母组成。在这里, S 和 T 具有相同的长度。

让 X 为空数组,重复以下操作,直到 S 等于 T:

  • 更改一个字符 S,并附加 S 到年底 X.

查找字符串数组 X 以这种方式获得的元素数量最少。如果有多个这样的元素数量最少的数组,则找到其中按字典顺序最小的一个。

字符串数组的字典顺序是什么?

一个字符串 S = S_1 S_2 \ldots S_N 长度 N is 按字典顺序较小 比字符串 T = T_1 T_2 \ldots T_N 长度 N 如果存在整数 1 \leq i \leq N 满足以下两个条件:

  • S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}
  • S_i 早于 T_i 按字母顺序排列。

字符串数组 X = (X_1,X_2,\ldots,X_M) 与 M 元素是 按字典顺序较小 比字符串数组 Y = (Y_1,Y_2,\ldots,Y_M) 与 M 元素(如果存在整数) 1 \leq j \leq M 满足以下两个条件:

  • (X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})
  • X_j 按字典顺序小于 Y_j.

约束

  • S 和 T 是由小写英文字母组成的字符串,长度介于 1 和 100,包括在内。
  • 的长度 S 和 T 相等。

输入

输入由标准输入按以下格式给出:

S
T

输出

让 M 是所需数组中的元素数量。打印 M + 1 行。

第一行应包含以下值 M.

的 i + 1第行 (1 \leq i \leq M) 应包含 i- 数组的第一个元素。


示例输入 1

adbe
bcbc

示例输出 1

3
acbe
acbc
bcbc

最初, 黑板上写着 S = adbe.

我们可以得到 X = ( acbe , acbc , bcbc ) 通过执行以下操作:

  • 更改 S to acbe 并附加 acbe 到年底 X.

  • 更改 S to acbc 并附加 acbc 到年底 X.

  • 更改 S to bcbc 并附加 bcbc 到年底 X.


示例输入 2

abcde
abcde

示例输出 2

0

示例输入 3

afwgebrw
oarbrenq

示例输出 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq