← 返回题目列表

AtCoder · genocon2021_b

B. 练习2

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

分数: 500 点

问题陈述

s 和 t 是由以下组成的字符串 A, C, G, T。我们表示 分别是 i第一个字符 s 和 t by s[i] 和 t[i]。我们定义以下分数 S_{sop} 并旨在通过添加空白符号来最大化它 s 和 t 在适当的位置。 s 和 t 添加空白符号后应相同,并且 N 表示长度。空白符号表示为 -.

S_{sop} = \sum_{i=1}^{N} sim(s[i], t[i])

sim(x,y) 是计算相似度的函数 x 和 y,下表定义了其输出。

x \ y A C G T -
A 1 -3 -3 -3 -5
C -3 1 -3 -3 -5
G -3 -3 1 -3 -5
T -3 -3 -3 1 -5
- -5 -5 -5 -5 -5

例如当 s=CTCGGT 和 t=CATCC, S_{sop} 最大化,如果 - 添加在第一个字符之后 s,并在最后一个字符之后添加两次 带有 balnk 符号的 t.

S_{sop} = sim(C, C)+sim(-,A)+sim(T,T)+sim(C,C)+sim(G,C)+sim(G,-)+ sim(T,-) = 1 + (-5) + 1 + 1 + (-3) + (-5) + (-5) = -15

请注意 s 和 t 被对齐,使得相同的字符出现在每个字符串的多个位置的相同位置。

C-TCGGT
CATCC--

我们称此任务为 成对比对 并将其描述为两行字符串。

给定两个字符串,输出其成对对齐,使其最大化 S_{sop}.

约束

  • s 和 t 是由以下组成的字符串 A, C, G, T.
  • 10 \leq |s|, |t| \leq 400 (字符串的长度 x 表示为 |x|.)

输入

输入由标准输入按以下格式给出:

s
t

输出

打印输入字符串的成对对齐,使得 S_{sop} 已最大化。 插入后 - in s 和 t,

s 应打印在第一行,并且 t 应打印在第二行。 如果有多个对齐方式可以最大化 S_{sop},您可以打印其中任意一项。

评审系统只能在以下情况下接受用户的输出: - 第一行/第二行等于输入的第一行/第二行如果 - 已删除。 - 第一行的长度等于第二行的长度。


样本输入 1

AGTTGAATTT
GTCGGACTTT

示例输出 1

AGT-TGAATTT
-GTCGGACTTT