← 返回题目列表

Codeforces · 254/C

C. 字谜

中文机器翻译题面 查看原题

如果我们可以重新排列字符串 x 中的字母并得到准确的字符串 y,则字符串 x 是字符串 y 的字谜词。例如,字符串“DOG”和“GOD”是字谜词,字符串“BABA”和“AABB”也是字谜词,但字符串“ABBAC”和“CAABA”则不是。

给定两个长度相同的字符串 s 和 t,由大写英文字母组成。您需要从字符串 s 中获取字符串 t 的字谜词。您可以执行替换操作:每个操作都是用任何其他字符替换字符串 s 中的某些字符。以最少次数的替换操作得到字符串 t 的字谜。如果你可以用最少的操作次数得到字符串 t 的多个字谜词,则得到字典顺序上最小的一个。

字符串的字典顺序就是我们熟悉的“字典”顺序。形式上,如果 p1 = q1,p2 = q2,...,pk - 1 = qk - 1,对于某些 k (1 ≤ k ≤ n),pk < qk,则长度为 n 的字符串 p 按字典顺序小于相同长度的字符串 q。这里字符串中的字符从1开始编号。字符串中的字符按照字母顺序进行比较。

输入

输入由两行组成。第一行包含字符串 s,第二行包含字符串 t。这些字符串具有相同的长度(1 到 105 个字符)并且由大写英文字母组成。

输出

在第一行打印 z — 从字符串 s 获取字符串 t 的字谜词所需的最少替换操作数。在第二行中打印可以在 z 操作中获得的字典顺序最小字谜词。

示例

输入 #1

ABA
CBA

输出 #1

1
ABC

输入 #2

CDBABC
ADCABD

输出 #2

2
ADBADC

注意

第二个样本有字符串 t 的八个字谜词,可以通过替换两个字母从字符串 s 获得:“ADBADC”、“ADDABC”、“CDAABD”、“CDBAAD”、“CDBADA”、“CDDABA”、“DDAABC”、“DDBAAC”。这些字谜词按字典顺序列出。字典顺序上最小的字谜是“ADBADC”。