本文共 1286 字,大约阅读时间需要 4 分钟。
假设字符串的基本操作仅为:删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
我们把进行了一次上述三种操作的任意一种操作称为进行了一步字符基本操作。 下面我们定义两个字符串的编辑距离:对于两个字符串a和b,通过上述的基本操作,我们可以把a变成b或b变成a,那么字符串a变成字符串b需要的最少基本字符操作步数称为字符串a和字符串b的编辑距离。 例如:a=“ABC”,b=“CBCD”,则a与b的编辑距离为2。 你的任务就是:编写一个快速的程序来计算任意两个字符串的编辑距离。输入包含两行:第一行为字符串A,第二行为字符串B。
字符串的长度不大于10000,且全为字母。输出只有一行,为编辑距离。
ABC
CBCD
0 | A1 | B2 | C3 |
C1 | 1 | 2 | 2 |
B2 | 2 | 1 | 2 |
C3 | 3 | 2 | 1 |
D4 | 4 | 3 | 2 |
2
#include#include #include #include using namespace std;const int MAXN = 5005;char dest[MAXN];char str[MAXN];int DP(int x, int y){ int i,j,temp; int **dp = new int *[x+1]; for(i=0;i<=x;i++) dp[i] = new int[y+1]; for(i=0;i<=x;i++) dp[i][0] = i; for(j=0;j<=y;j++) dp[0][j] = j; for(i=1;i<=x;i++) { for(j=1;j<=y;j++) { temp = min(dp[i-1][j] + 1,dp[i][j-1] + 1); if(dest[i-1] == str[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1; } } } temp = dp[x][y]; for(i=0;i<=x;i++) delete []dp[i]; delete []dp; return temp;}int main(){ freopen("in.txt","r",stdin); cin>>dest>>str; int dest_len = strlen(dest); int str_len = strlen(str); cout< <
转载地址:http://mtyhj.baihongyu.com/