如何比較兩個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次操作（插入、刪除或替換）就可以將一個字符串轉換為另一個字符串。