103702: [Atcoder]ABC370 C - Word Ladder

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：8 Solved：0

Description

Score : $300$ points

Problem Statement

You are given two strings $S$ and $T$ consisting of lowercase English letters. Here, $S$ and $T$ have equal lengths.

Let $X$ be an empty array, and repeat the following operation until $S$ equals $T$:

  • Change one character in $S$, and append $S$ to the end of $X$.

Find the array of strings $X$ with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

What is lexicographical order on arrays of strings?

A string $S = S_1 S_2 \ldots S_N$ of length $N$ is lexicographically smaller than a string $T = T_1 T_2 \ldots T_N$ of length $N$ if there exists an integer $1 \leq i \leq N$ such that both of the following are satisfied:

  • $S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}$
  • $S_i$ comes earlier than $T_i$ in alphabetical order.

An array of strings $X = (X_1,X_2,\ldots,X_M)$ with $M$ elements is lexicographically smaller than an array of strings $Y = (Y_1,Y_2,\ldots,Y_M)$ with $M$ elements if there exists an integer $1 \leq j \leq M$ such that both of the following are satisfied:

  • $(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})$
  • $X_j$ is lexicographically smaller than $Y_j$.

Constraints

  • $S$ and $T$ are strings consisting of lowercase English letters with length between $1$ and $100$, inclusive.
  • The lengths of $S$ and $T$ are equal.

Input

The input is given from Standard Input in the following format:

$S$
$T$

Output

Let $M$ be the number of elements in the desired array. Print $M + 1$ lines.

The first line should contain the value of $M$.

The $i + 1$-th line $(1 \leq i \leq M)$ should contain the $i$-th element of the array.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, $S =$ adbe.

We can obtain $X = ($ acbe $,$ acbc $,$ bcbc $)$ by performing the following operations:

  • Change $S$ to acbe and append acbe to the end of $X$.

  • Change $S$ to acbc and append acbc to the end of $X$.

  • Change $S$ to bcbc and append bcbc to the end of $X$.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Output

得分：300分

问题陈述

给定两个由小写英文字母组成的字符串$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 \leq i \leq 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 \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$之间，包括$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。

我们可以通过执行以下操作将$S$变为$X = ($ acbe $,$ acbc $,$ bcbc $)$：

  • 将$S$更改为acbe并将acbe附加到$X$的末尾。

  • 将$S$更改为acbc并将acbc附加到$X$的末尾。

  • 将$S$更改为bcbc并将bcbc附加到$X$的末尾。

示例输入2

abcde
abcde

示例输出2

0

Source/Category

加入题单

上一题 下一题 算法标签：