如何比較兩個(gè)C語(yǔ)言字符串的相似性

要比較兩個(gè)C語(yǔ)言字符串的相似性，可以使用一種稱為“編輯距離”（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;
}

這個(gè)程序首先計(jì)算輸入字符串的長(zhǎng)度，并分配一個(gè)動(dòng)態(tài)二維數(shù)組來(lái)存儲(chǔ)中間結(jié)果。接下來(lái)，它初始化第一行和第一列的值，然后遍歷每個(gè)字符，計(jì)算編輯距離。最后，返回dp[len1][len2]作為結(jié)果，并釋放分配的內(nèi)存。

在這個(gè)例子中，我們計(jì)算了字符串 “kitten” 和 “sitting” 之間的編輯距離。運(yùn)行此程序?qū)⑤敵觯?/p>

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

這意味著只需要3次操作（插入、刪除或替換）就可以將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串。