#genocon2021b. [genocon2021_b]Practice 2

[genocon2021_b]Practice 2

给定两个完全由A,C,G,T组成的字符串 s,ts,t ,将 s,ts,t 的第 ii 个字符记为 si,tis_i,t_i 。现在要在 s,ts,t 中各插入一个-,使得两个字符串的相似度最高。请输出一组符合要求的修改之后的 s,ts,t

对于字符 aabb 来说,它们的相似度计算方法如下:

  • 如果 aabb 中至少有一个为-,则它们的相似度为 5-5
  • 否则,如果 aabb 相同,则它们的相似度为 11
  • 否则, aabb 的相似度为 3-3

两个字符串的相似度为各字符的相似度之和。记 sim(si,ti)sim(s_i,t_i)sis_itit_i 的相似度,nn 为两个字符串的长度,则 sstt 的相似度就为 sim(s1,t1)+sim(s2,t2)+...+sim(sn,tn)sim(s_1,t_1)+sim(s_2,t_2)+...+sim(s_n,t_n) 的结果。(本题中,字符串下标从 11 开始。)