首页C语言实现：用动态规划算法实现：求两个字符串的最短编辑距离：字符串1：FRAME 字符串2：FAMILY，两个

C语言实现：用动态规划算法实现：求两个字符串的最短编辑距离：字符串1：FRAME 字符串2：FAMILY，两个

时间: 2024-11-09 11:30:27 AIGC 浏览: 77

在C语言中，我们可以使用动态规划(Dynamic Programming)来计算两个字符串之间的最短编辑距离，也被称为Levenshtein距离，通常用于比较文本相似度。这里是一个简单的例子，假设我们有两个字符串 "STRING1" 和 "STRING2"： ```c #include <stdio.h> #include <string.h> int min(int a, int b, int c) { return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c); } int editDistance(char *str1, char *str2, int m, int n) { int dp[m + 1][n + 1]; // 初始化第一行和第一列 for (int i = 0; i <= m; i++) { dp[i][0] = i; } for (int j = 0; j <= n; j++) { dp[0][j] = j; } // 计算编辑距离矩阵 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1; } } } return dp[m][n]; } int main() { char str1[] = "FRAME"; char str2[] = "FAMILY"; int m = strlen(str1); int n = strlen(str2); printf("The minimum number of operations required to make the two strings equal is %d.\n", editDistance(str1, str2, m, n)); return 0; } ``` 在这个程序中，`editDistance` 函数使用了一个二维数组 `dp` 来存储每个位置上两个子串的最小编辑距离。最后，函数返回整个字符串对的最小编辑距离。

阅读全文

CSDN会员

开通CSDN年卡参与万元壕礼抽奖

海量 VIP免费资源千本正版电子书商城会员专享价千门课程&专栏

全年可省5,000元立即开通全年可省5,000元立即开通