用C语言编写给定一个原始字符串S1和一个目标字符串S2,将S1到S2的编辑距离定义为S1编辑操作成S2所需的最小编辑次数。编辑操作包括插入一个字符、删除一个字符及替换一个字符。分行输入两个字符串S1和S2。输出S1和S2 的编辑距离。
时间: 2024-03-09 12:44:23 浏览: 74
好的,这是一个经典的字符串问题,可以使用动态规划算法来解决。以下是C语言实现代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int min(int a, int b, int c) {
int min_val = a;
if (b < min_val) min_val = b;
if (c < min_val) min_val = c;
return min_val;
}
int edit_distance(char s1[], char s2[], int len1, int len2) {
int dp[MAX_LEN][MAX_LEN];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
int cost = (s1[i-1] == s2[j-1]) ? 0 : 1;
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost);
}
}
}
return dp[len1][len2];
}
int main() {
char s1[MAX_LEN], s2[MAX_LEN];
printf("Enter string s1: ");
scanf("%s", s1);
printf("Enter string s2: ");
scanf("%s", s2);
int len1 = strlen(s1), len2 = strlen(s2);
int dist = edit_distance(s1, s2, len1, len2);
printf("Edit distance between s1 and s2: %d\n", dist);
return 0;
}
```
输入示例:
```
Enter string s1: kitten
Enter string s2: sitting
```
输出示例:
```
Edit distance between s1 and s2: 3
```
注意:此代码实现仅适用于字符串长度不超过100的情况。如果需要处理更长的字符串,需要使用动态数组或其他数据结构来存储动态规划表。
阅读全文