分数: 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