1

我正在编写一个代码来计算两个给定字符串 t 和 s 的编辑距离，其中 m = strlen(t) 和 n = strlen(s)，并且代码应该只使用 O(m) 中的内存。此外，计算两个大约 50 个字符的字符串的时间不应超过 4 秒。我编写的代码满足后者，但我不确定第一个，所以如果你能检查它是否使用不超过 O(m) 的内存，我会很高兴。如果没有，听到一些提示如何做到这一点也很有用。谢谢。

#include <stdio.h>

/************************************/
/* TODO: Insert possible help       */
/*       functions in here          */
/************************************/

int min (int a[], int l) {
    int i, min = a[0];
    for (i = 1; i < l; i++) {
        if (a[i] < min) {
            min = a[i];
        }
    }
    return min;
}

int main() {
    /* n, m, s, t are configurable in the source, i.e. the values here are 
            only an example and shall be changed to any value.*/
    const int n = 58; /* length of s, > 0 */
    const int m = 54; /* length of t, > 0 */
    char *s = "Calculateanddisplaythenumberofcharacterswithinarewrwegurie";
    char *t = "Simplycopyeverythinginsideandpasteitwhereogwrgheigrber";

/* Save the edit distance in res */
    int res;

int matrix[n+1][m+1];

int i, j;

for (i = 0; i <= m; i++) {
        matrix[n][i] = m-i;
    }
    for (i = 0; i <= n; i++) {
        matrix[i][m] = n-i;
    }

for (i = n-1; i >= 0; i--) {
        for (j = m-1; j >= 0; j--) {
        int cost = (s[i] != t[j]);
        int b[3];
        b[0] = 1+matrix[i][j+1];
        b[1] = 1+matrix[i+1][j];
        b[2] = matrix[i+1][j+1]+cost;
        matrix[i][j] = min(b, 3);
        }
    }

res = matrix[0][0];

/* Output */
    printf("The edit distance is %d.\n\n", res);
    return 0;
}
4

1 回答 1

0

你只需要在矩阵中回看 1 行，所以第三行可以和第一行在同一个地方，第四行可以和第二行在同一个地方，依此类推。你只需要在矩阵中的两行矩阵。所以：

int matrix[n+1][m+1];

变成

int matrix[2][m + 1];
于 2012-12-26T06:45:55.027 回答