/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
英小文字からなる文字列 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 は英小文字からなる長さ 1 以上 100 以下の文字列
- S と T の長さは等しい
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
答えの要素数を M として M + 1 行出力せよ。
1 行目には M の値を出力せよ。
i + 1 (1 \leq i \leq M) 行目には答えの i 番目の要素を出力せよ。
入力例 1
adbe bcbc
出力例 1
3 acbe acbc bcbc
はじめ、S = adbe です。
以下のように操作することで、X = ( acbe , acbc , bcbc ) とすることができます。
-
S を
acbeに書き換え、X の末尾にacbeを追加する。 -
S を
acbcに書き換え、X の末尾にacbcを追加する。 -
S を
bcbcに書き換え、X の末尾にbcbcを追加する。
入力例 2
abcde abcde
出力例 2
0
入力例 3
afwgebrw oarbrenq
出力例 3
8 aawgebrw aargebrw aarbebrw aarbebnw aarbebnq aarbeenq aarbrenq oarbrenq
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
acbeand appendacbeto the end of X. -
Change S to
acbcand appendacbcto the end of X. -
Change S to
bcbcand appendbcbcto 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