单词阶梯

题目描述

给你两个由小写英文字母组成的字符串 $S$ 和 $T$。这里,$S$ 与 $T$ 长度相等。

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

修改 $S$ 中的一个字符,并将 $S$ 追加到 $X$ 的末尾。

求按这种方式得到的元素个数最少的字符串数组 $X$。若元素个数最少的数组有多个,求其中字典序最小的一个。

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

长度为 $N$ 的字符串 $S = S_1 S_2 \ldots S_N$ 比长度为 $N$ 的字符串 $T = T_1 T_2 \ldots T_N$ 字典序更小,当且仅当存在整数 $1 \le i \le N$,同时满足以下两个条件:

• $S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}$
• $S_i$ 在字母表中比 $T_i$ 更靠前。

有 $M$ 个元素的字符串数组 $X = (X_1,X_2,\ldots,X_M)$ 比有 $M$ 个元素的字符串数组 $Y = (Y_1,Y_2,\ldots,Y_M)$ 字典序更小,当且仅当存在整数 $1 \le j \le M$,同时满足以下两个条件:

• $(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})$
• $X_j$ 比 $Y_j$ 字典序更小。

输入格式

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

$S$
$T$

输出格式

设目标数组的元素个数为 $M$。输出 $M + 1$ 行。

第 1 行输出 $M$ 的值。

第 $i + 1$ 行 $(1 \le i \le M)$ 输出数组的第 $i$ 个元素。

样例

adbe
bcbc

3
acbe
acbc
bcbc

初始时,$S =$ adbe。

通过如下操作可以得到 $X = ($ acbe $,$ acbc $,$ bcbc $)$:

将 $S$ 改为 acbe,并将 acbe 追加到 $X$ 末尾。

将 $S$ 改为 acbc,并将 acbc 追加到 $X$ 末尾。

将 $S$ 改为 bcbc,并将 bcbc 追加到 $X$ 末尾。

abcde
abcde

0

afwgebrw
oarbrenq

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

数据范围

• $S$、$T$ 是由小写英文字母组成的字符串,长度在 $1$ 到 $100$ 之间(含两端)。
• $S$ 与 $T$ 的长度相等。