-
大小: 1KB文件類型: .rar金幣: 2下載: 0 次發布日期: 2021-05-27
- 語言: 其他
- 標簽:
資源簡介
字符串比較問題
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??>?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-1][j-1]?+?abs(A[i-1]-B[j-1]);
if?(i?&&?(s[i-1][j]?+?k? s[i][j]?=?s[i-1][j]?+?k;
if?(j?&&?(s[i][j-1]?+?k? 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
評論
共有 條評論