【題目描述】

對于兩個不同的字符串，我們有一套操作方法來把他們變得相同，具體方法為： ? ?

????修改一個字符（如把“a”替換為“b”）;

????刪除一個字符（如把“traveling”變為“travelng”）。

比如對于“abcdefg”和“abcdef”兩個字符串來說，我們認為可以通過增加/減少一個“g”的方式來達到目的。無論增加還是減少“g”，我們都僅僅需要一次操作。我們把這個操作所需要的次數定義為兩個字符串的距離。

給定任意兩個字符串，寫出一個算法來計算出他們的距離。

【輸入】

第一行有一個整數n。表示測試數據的組數。

接下來共n行，每行兩個字符串，用空格隔開，表示要計算距離的兩個字符串。

字符串長度不超過1000。

【輸出】

針對每一組測試數據輸出一個整數，值為兩個字符串的距離。

【輸入樣例】

3
abcdefg? abcdef
ab ab
mnklj jlknm

【輸出樣例】

1
0
4

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; char a[N],b[N]; int f[N][N]; int main() {int n;cin>>n;while(n--){scanf("%s%s",a+1,b+1);int len_a=strlen(a+1);int len_b=strlen(b+1);for(int i=0;i<=len_a;i++)f[i][0]=i;for(int j=0;j<=len_b;j++)f[0][j]=j;for(int i=1;i<=len_a;i++)for(int j=1;j<=len_b;j++){if(a[i]==b[j])f[i][j]=f[i-1][j-1];elsef[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;}cout<<f[len_a][len_b]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的计算字符串距离（信息学奥赛一本通-T1298）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。