#D0960. 最优替换表

最优替换表

最优替换表

33DAI 想把一个字母串「伪装」成另一个字母串。他决定使用一张替换表:给 1010 个小写字母 a 到 j 各指定一个小写字母作为它的替身,并且不同字母的替身互不相同。也就是说,这张替换表是 a 到 j 的一个排列。

现在给定两个长度都是 nn 的小写字母串 SS 和 TT,保证其中只出现 a 到 j 这 1010 个字母。把 SS 的每一位都按替换表改写,得到 S′S'。记匹配位数为 S′S' 与 TT 相同位置的个数。

请你选出一张替换表,使匹配位数尽可能大。如果有多张替换表都能达到最大值,输出其中字典序最小的那一张:把替换表看成 1010 个字符组成的字符串,第 11 个字符是 a 的替身,第 22 个字符是 b 的替身,……,第 1010 个字符是 j 的替身,两个替换表按这个字符串的字典序比较。

输入格式

  • 第一行一个长度为 nn 的字符串 SS。
  • 第二行一个长度为 nn 的字符串 TT。

输出格式

  • 输出一行一个长度为 1010 的字符串,表示你选出的替换表。
ab
ba
bacdefghij
abc
bca
bcadefghij
a
a
abcdefghij

数据范围

  • 1≤n≤2×1051 \le n \le 2 \times 10^5
  • SS 与 TT 只包含 a 到 j 这 1010 个小写字母,长度都为 nn。

子任务设置

  • 子任务 1(30 分):SS 与 TT 中出现的不同字母总数不超过 44。
  • 子任务 2(30 分):SS 与 TT 中出现的不同字母总数不超过 88。
  • 子任务 3(40 分):无特殊限制。