给定两个完全由A
,C
,G
,T
组成的字符串 s,t ,将 s,t 的第 i 个字符记为 si,ti 。现在要在 s,t 中各插入一个-
,使得两个字符串的相似度最高。请输出一组符合要求的修改之后的 s,t 。
对于字符 a 和 b 来说,它们的相似度计算方法如下:
-
,则它们的相似度为 −5 。两个字符串的相似度为各字符的相似度之和。记 sim(si,ti) 为 si 和 ti 的相似度,n 为两个字符串的长度,则 s 与 t 的相似度就为 sim(s1,t1)+sim(s2,t2)+...+sim(sn,tn) 的结果。(本题中,字符串下标从 1 开始。)