第10次上机实验题目（序列比对和字符转换）#

---

利用动态规划算法实现

| 1 序列比对 【问题描述】 设S1[1..n]和S2[1..m]是两个序列, 把它们并排放到一起进行比较,在比较时可以在某个序列的字符 之间插入空格, 插入空格的目的是使它们局部的相同区域能够对应. (1)如果两个对应字符相等,那么赋权值 2; (2)如果对应字符不等,赋权值-2; (3)如果一个是字符,一个是空格,赋权值-1. 求权值最大的对准方式。 【输入形式】输入两个序列 【输出形式】最大权值 【样例输入】 axabcdes axbacfes 【样例输出】

8

字符转换

问题描述#

设A和B是2个字符串。要用最少的字符串操作将字符串A转换为字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符。

将字符串A变为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出他们的编辑距离d(AB)。

输入格式#

第一行是字符串A，第二行是字符串B。

输出格式#

输出编辑距离d(A,B)。

样例输入#

vintner
writers

样例输出#

6