TA的每日心情 | 开心
2024-11-2 01:25 |
|---|
签到天数: 102 天 [LV.6]常住居民II
七彩门番
 
- 积分
- 4081
|
发表于 2024-9-7 22:02:52
|
显示全部楼层
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?
讯飞听见 翻译
###问题陈述
给出两个由小写英文字母组成的字符串
S 和
T 。
这里，
S 和
T 的长度相等。设
X 为空数组，重复以下操作，直到
S 等于
T ：
-在
S 中更改一个字符，
并将
S 附加到
X 的末尾。找到以这种方式获得的最小元素数的字符串数组
X 。
如果有多个这样的数组具有最小数量的元素，则找出其中字典序上最小的一个。什么是字符串数组的字典顺序？
长度为
N 的字符串
S=S
1
​
S
2
​
…S
N
​
在字典序上**小于长度为
N 的字符串
T=T
1
​
T
2
​
…T
N
​
，如果存在整数{
1≤i≤N 满足以下两个条件：
S
1
​
S
2
​
…S
i−1
​
=T
1
​
T
2
​
…T
i−1
​
S
i
​
按字母顺序早于
T
i
​
。
包含
M 元素的字符串数组
X=(X
1
​
,X
2
​
,…,X
M
​
) 在字典顺序上**小于包含
M 元素的字符串数组
Y=(Y
1
​
,Y
2
​
,…,Y
M
​
)
如果存在整数
1≤j≤M ，则满足以下两个条件：
(X
1
​
,X
2
​
,…,X
j−1
​
)=(Y
1
​
,Y
2
​
,…,Y
j−1
​
)
X
j
​
在字典序上小于
N
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≤i≤M) should contain the
i-th element of the array.
Sample Input 1
Copy
adbe
bcbc
Sample Output 1
Copy
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
Copy
abcde
abcde
Sample Output 2
Copy
0
Sample Input 3
Copy
afwgebrw
oarbrenq
Sample Output 3
Copy
8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq |
|
楼主: FandaP
狗仔卡
显身卡
楼主