分数: 500 点
问题陈述
s 和 t 是由以下组成的字符串
S_{sop} = \sum_{i=1}^{N} sim(s[i], t[i])
sim(x,y) 是计算相似度的函数 x 和 y,下表定义了其输出。
| x \ y | |||||
| 1 | -3 | -3 | -3 | -5 | |
| -3 | 1 | -3 | -3 | -5 | |
| -3 | -3 | 1 | -3 | -5 | |
| -3 | -3 | -3 | 1 | -5 | |
| -5 | -5 | -5 | -5 | -5 |
例如当 s=
S_{sop} = sim(
请注意 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} 已最大化。
插入后
s 应打印在第一行,并且 t 应打印在第二行。 如果有多个对齐方式可以最大化 S_{sop},您可以打印其中任意一项。
评审系统只能在以下情况下接受用户的输出:
- 第一行/第二行等于输入的第一行/第二行如果
样本输入 1
AGTTGAATTT GTCGGACTTT
示例输出 1
AGT-TGAATTT -GTCGGACTTT