#10990. C - Word Ladder 单词阶梯 比赛编号370

C - Word Ladder 单词阶梯 比赛编号370

[ABC370C] Word Ladder

题面翻译

题目描述

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

新开一个数组 XX ,并重复以下操作,直到 SSTT 相等:

更改 SS 中的一个字符,并将修改之后的 SS 添加到到 XX 的末尾。

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

输入格式

两行 分别代表字符串 SSTT (令长度为 lenlen )

输出格式

第一行输出修改的次数 (设它为 MM )

接下来 MM 行,输出 XX 数组,每一行输出 lenlen 个字符。

(我这里的表述与原题干有区别,如有歧义请大佬们指出qwq)

题目描述

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

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

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

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

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

  • S1 S2  Si1 = T1 T2  Ti1 S_1\ S_2\ \ldots\ S_{i-1}\ =\ T_1\ T_2\ \ldots\ T_{i-1}
  • Si S_i Ti T_i よりアルファベット順で早い。

要素数 M M の文字列の配列 X = (X1,X2,,XM) X\ =\ (X_1,X_2,\ldots,X_M) が要素数 M M の文字列の配列 Y = (Y1,Y2,,YM) Y\ =\ (Y_1,Y_2,\ldots,Y_M) より辞書順で小さいとは、ある整数 1  j  M 1\ \leq\ j\ \leq\ M が存在して下記の 2 2 つがともに成り立つことをいいます。

  • (X1,X2,,Xj1) = (Y1,Y2,,Yj1) (X_1,X_2,\ldots,X_{j-1})\ =\ (Y_1,Y_2,\ldots,Y_{j-1})
  • Xj X_j Yj Y_j より辞書順で小さい。

输入格式

入力は以下の形式で標準入力から与えられる。

S S T T

输出格式

答えの要素数を M M として M + 1 M\ +\ 1 行出力せよ。

1 1 行目には M M の値を出力せよ。

i + 1 (1  i  M) i\ +\ 1\ (1\ \leq\ i\ \leq\ M) 行目には答えの i 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 S,\ T は英小文字からなる長さ 1 1 以上 100 100 以下の文字列
  • S S T T の長さは等しい

Sample Explanation 1

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