如何比较两个C语言字符串的相似性

要比较两个C语言字符串的相似性，可以使用一种称为“编辑距离”（Edit Distance）的算法

#include<stdio.h>
#include<string.h>
#include <stdlib.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int edit_distance(const char *str1, const char *str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    int **dp = (int **)malloc((len1 + 1) * sizeof(int *));
    for (int i = 0; i <= len1; i++) {
        dp[i] = (int *)malloc((len2 + 1) * sizeof(int));
    }

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
            }
        }
    }

    int distance = dp[len1][len2];

    for (int i = 0; i <= len1; i++) {
        free(dp[i]);
    }
    free(dp);

    return distance;
}

int main() {
    const char *str1 = "kitten";
    const char *str2 = "sitting";

    printf("Edit distance between '%s' and '%s': %d\n", str1, str2, edit_distance(str1, str2));

    return 0;
}

这个程序首先计算输入字符串的长度，并分配一个动态二维数组来存储中间结果。接下来，它初始化第一行和第一列的值，然后遍历每个字符，计算编辑距离。最后，返回dp[len1][len2]作为结果，并释放分配的内存。

在这个例子中，我们计算了字符串 “kitten” 和 “sitting” 之间的编辑距离。运行此程序将输出：

Edit distance between 'kitten' and 'sitting': 3

这意味着只需要3次操作（插入、删除或替换）就可以将一个字符串转换为另一个字符串。