3888: 4.4 DNA基因鉴定——编辑距离

编辑距离是指将一个字符串变换为另一个字符串所需要的最小编辑操作。 

给定两个序列 X={x1，x2，x3，…，xm}和 Y={y1，y2，y3，…，yn}，找出 X 和 Y 的编辑 距离。 例如：X=（A，B，C，D，A，B），Y=（B，D，C，A，B）。如果用穷举法，会有很多 种对齐方式，暴力穷举的方法是不可取的。那么怎么找到编辑距离呢？ 

给你一个T，表示有T组数据（1<=T<=10）

给你两个字符串是s1,s2

s1,s2的长度<=1000