[ABC370C] Word Ladder

题面翻译

题目描述

有两个由小写英文字母组成的字符串 $S$ 和 $T$ 。其中保证 $S$ 和 $T$ 的长度相等。

新开一个数组 $X$ ，并重复以下操作，直到 $S$ 与 $T$ 相等：

更改 $S$ 中的一个字符，并将修改之后的 $S$ 添加到到 $X$ 的末尾。

求以这种方式获得的元素数量最少的字符串数组 $X$ 。如果有多个这样的数组，其元素数量最少，输出字典序最小的一个即可。

输入格式

两行 分别代表字符串 $S$ 和 $T$ （令长度为 $len$ )

输出格式

第一行输出修改的次数 （设它为 $M$ )

接下来 $M$ 行，输出 $X$ 数组，每一行输出 $len$ 个字符。

（我这里的表述与原题干有区别，如有歧义请大佬们指出qwq）

题目描述

英小文字からなる文字列 $S,\ T$ が与えられます。ここで、$S$ と $T$ の長さは等しいです。

$X$ を空の配列とし、以下の操作を $S$ と $T$ が等しくなるまで繰り返します。

• $S$ の文字を $1$ 文字書き換え、$X$ の末尾に $S$ を追加する。

こうして得られる文字列の配列 $X$ のうち要素数最小のものを求めてください。要素数最小のものが複数考えられる場合は、そのうち辞書順最小のものを求めてください。

文字列の配列の辞書順とは長さ $N$ の文字列 $S\ =\ S_1\ S_2\ \ldots\ S_N$ が長さ $N$ の文字列 $T\ =\ T_1\ T_2\ \ldots\ T_N$ より辞書順で小さいとは、ある整数 $1\ \leq\ i\ \leq\ N$ が存在して下記の $2$ つがともに成り立つことをいいます。

• $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\ \leq\ j\ \leq\ M$ が存在して下記の $2$ つがともに成り立つことをいいます。

• $(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\ \leq\ i\ \leq\ M)$ 行目には答えの $i$ 番目の要素を出力せよ。

样例 #1

样例输入 #1

adbe
bcbc

样例输出 #1

3
acbe
acbc
bcbc

样例 #2

样例输入 #2

abcde
abcde

样例输出 #2

0

样例 #3

样例输入 #3

afwgebrw
oarbrenq

样例输出 #3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

提示

制約

• $S,\ T$ は英小文字からなる長さ $1$ 以上 $100$ 以下の文字列
• $S$ と $T$ の長さは等しい

Sample Explanation 1

はじめ、$S\ =$ adbe です。 以下のように操作することで、$X\ =\ ($ acbe $,$ acbc $,$ bcbc $)$ とすることができます。 - $S$ を acbe に書き換え、$X$ の末尾に acbe を追加する。 - $S$ を acbc に書き換え、$X$ の末尾に acbc を追加する。 - $S$ を bcbc に書き換え、$X$ の末尾に bcbc を追加する。