另類編輯距離
題目詳情:
傳統的編輯距離里面有三種操作，即增、刪、改，我們現在要討論的編輯距離只允許兩種操作，即增加一個字符、洗掉一個字符。我們求兩個字串的這種編輯距離，即把一個字串變成另外一個字串的最少操作次數。
輸入格式：
多組資料，每組資料兩行，每行一個字串。每個字串長度不超過1000，只有大寫英文字母組成。
輸出格式：
每組資料輸出一行包含一個整數，表示需要最少操作的次數。
答題說明:
輸入樣例
A
ABC
BC
A
輸出樣例：
2
3
我的程式，在VS上運行沒有錯誤，可是提交說結果不對，怎么回事呢，求大神指點一下。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//計算本程式中的編輯距離
int caldist(string str1,string str2)
{
int dist=0;
int len1,len2;
len1=str1.length();
len2=str2.length();
//計算最大公共子序列
vector<vector<int>> map;//map[len1][len2]
vector<int> temp;
for(int i=0;i<=len2;i++)
{
temp.push_back(0);
}
for(int i=0;i<=len1;i++)
{
map.push_back(temp);
}
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(str1[i]==str2[j])
{
map[i+1][j+1]=map[i][j]+1;
}
else
{
map[i+1][j+1]=max(map[i+1][j],map[i][j+1]);
}
}
}
/*
for(int i=0;i<=len1;i++)
{
for(int j=0;j<=len2;j++)
{
cout<<map[i][j]<<" ";
}
cout<<endl;
}*/
dist=map[len1][len2];
//兩個字串的長度和-最大公共子序列*2，即是結果
dist=len1+len2-dist*2;
return dist;
}
int main()
{
string str1,str2;
const int T=10;//T組輸入
int dist[T];
for(int i=0;i<T;i++)
{
cin>>str1;
cin>>str2;
dist[i]=caldist(str1,str2);
}
cout<<endl;
for(int i=0;i<T;i++)
{
cout<<dist[i]<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/102974.html
標籤：基礎類
下一篇：struct says