小A最近一直在找自己的爸爸，用什么办法呢，就是DNA比对， 小A有一套自己的DNA序列比较方法，其最终目标是最大化两个DNA序列的相似程度，具体步骤如下： 1.给出两个DNA序列，第一个长度为nnn,第二个长度为mmm. 2.在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同 3.逐位进行匹配，如果两个序列相同位置上的字符都不是空格,假设第一
小A最近一直在找自己的爸爸，用什么办法呢，就是DNA比对。 小A有一套自己的DNA序列比较方法，其最终目标是最大化两个DNA序列的相似程度，具体步骤如下： 1.给出两个DNA序列，第一个长度为nnn,第二个长度为mmm. 2.在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同 3.逐位进行匹配，如果两个序列相同位置上的字符都不是空格,假设第一个是xxx,第二个是yyy,那么他们的相似程度由d(x,y)d(x,y)d(x,y)定义。对于两个序列中任意一段极长的长度为kkk 的连续空格，我们定义这段空格的相似程度为g(k)=−A−B(k−1)g(k)=-A-B(k-1)g(k)=−A−B(k−1)。 那么最终两个序列的相似程度就是所有的d(x,y)d(x,y)d(x,y)加上所有的极长空格段的相似程度之和。 现在小A通过某种奥妙重重的方式得到了小B的DNA序列中的一段，他想请你帮他算一下小A的DNA序列和小B的DNA序列的最大相似程度。
（图片来源网络，侵删）
标签： HBC14499找爸爸题解
