【題目描述】

設A和B是兩個字符串。我們要用最少的字符操作次數，將字符串A轉換為字符串B。這里所說的字符操作共有三種：

????1、刪除一個字符；

????2、插入一個字符；

????3、將一個字符改為另一個字符。

對任意的兩個字符串A和B，計算出將字符串A變換為字符串B所用的最少字符操作次數。

【輸入】

第一行為字符串A；第二行為字符串B；字符串A和B的長度均小于2000。

【輸出】

只有一個正整數，為最少字符操作次數。

【輸入樣例】

sfdqxbw
gfdgw

【輸出樣例】

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 3001 #define MOD 2520 #define E 1e-12 using namespace std; char a[N],b[N]; int f[N][N]; int main() {scanf("%s%s",a+1,b+1);int n=strlen(a+1);int m=strlen(b+1);for(int i=1;i<=n;i++)f[i][0]=i;for(int i=1;i<=m;i++)f[0][i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i]==b[j])f[i][j]=f[i-1][j-1];elsef[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;cout<<f[n][m]<<endl;return 0; }

?

總結

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

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