5815: 4.4 DNA基因鉴定
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：154
解决：71
题目描述
我们经常会听说DNA 亲子鉴定是怎么回事呢?人类的 DNA由4个基本字母{A,C，G,T}构成,包含了多达30亿个字符。如果两个人的DNA序列相差0.1%，仍然意味着有300万个位置不同，所以我们通常看到的DNA 亲子鉴定报告上结论有:相似度99.99%，不排除亲子关系。
怎么判断两个基因的相似度呢?生物学上给出了一种编辑距离的概念。
例如两个字符串 FAMILY和frame,有两种对齐方式:
F - A M I L Y - F A M I L Y
F R A M E F R A M E
第1种对齐需要付出的代价:4，插入R，将Ⅰ替换为E，删除L、Y。
第2种对齐需要付出的代价:5，插入R，将F替换为R，将I替换为E，删除L、Y。编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。
怎么找到两个字符串x[1，…,m]和y[1，…，n]的编辑距离呢?
怎么判断两个基因的相似度呢?生物学上给出了一种编辑距离的概念。
例如两个字符串 FAMILY和fr
F - A M I L Y - F A M I L Y
F R A M E F R A M E
第1种对齐需要付出的代价:4，插入R，将Ⅰ替换为E，删除L、Y。
第2种对齐需要付出的代价:5，插入R，将F替换为R，将I替换为E，删除L、Y。编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。
怎么找到两个字符串x[1，…,m]和y[1，…，n]的编辑距离呢?
输入
样例组数
t （0 < t < 100）
输入字符串 ( 字符串长度小于1000）
S1
输入字符串
S2
t （0 < t < 100）
输入字符串 ( 字符串长度小于1000）
S1
输入字符串
S2
输出
两个字符串的编辑距离
d
d
样例输入 复制
1
family
frame样例输出 复制
4提示
趣学算法