字符串比较问题对于长度相同的2 个字符串A和B，其距离定义为相应位置字符距离之和。2 个非空格

字符串比较问题 Description ?问题描述： 对于长度相同的2 个字符串A和B，其距离定义为相应位置字符距离之和。2 个非空格 字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距 离为一定值k。 在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干 空格字符所产生的字符串。在字符串A 和B 的所有长度相同的扩展中，有一对距离最小的 扩展，该距离称为字符串A和B的扩展距离。 对于给定的字符串A和B，试设计一个算法，计算其扩展距离。 ?编程任务： 对于给定的字符串A和B，编程计算其扩展距离。 Input 由文件input.txt给出输入数据。第1 行是字符串A；第2 行是字符串B。第3行是空格 与其它字符的距离定值k。 Output 将计算出的字符串A和B的扩展距离输出到文件output.txt。 Sample Input cmc snmn 2 Sample Output 10

#include 
#include 
#include 
#include 
using namespace std;
ifstream cin（“1.in“）;
ofstream cout（“1.out“）;
//v[i][j] =min{v[i-1][j]+kv[ij-1]+kv[i-1][j-1]+dist（aibj）}
//v[i-1][j]+k A中加空格
//v[i][j-1]+k B中加空格
//v[i-1][j-1]+ dist[aibj] A和B都不加空格
int main（）
{
	string AB;
	int k;
	cin >> A >> B >> k;
	int len1 = A.length（）;
	int len2 = B.length（）;

	vector < vector  > s（len1 + 1vector（len2 + 1））;

	for（int i = 0; i <= len1; i++）
		for（int j = 0; j <= len2; j++）
		{			
			if （i + j）
			{
				s[i][j] = INT_MAX;
				if （（i*j） && （s[i-1][j-1] + abs（A[i-1]-B[j-1]） < s[i][j]））
					s[i][j] = s[i-1][j-1] + abs（A[i-1]-B[j-1]）;
				if （i && （s[i-1][j] + k < s[i][j]））
					s[i][j] = s[i-1][j] + k;
				if （j && （s[i][j-1] + k < s[i][j]））
					s[i][j] = s[i][j-1] + k;					
			}
		}
	return 0;	
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        890  2008-11-24 22:35  字符串比较问题\1039.cpp

     文件        762  2009-03-13 19:09  字符串比较问题\字符串比较问题.txt

     目录          0  2009-03-13 19:10  字符串比较问题

----------- ---------  ---------- -----  ----

                 1652                    3