c - O(m) のメモリを必要とする C のレーベンシュタイン距離

Question

m = strlen(t) および n = strlen(s) で指定された 2 つの文字列 t および s の編集距離を計算するコードを書いています。コードは O(m) のメモリのみを使用する必要があります。さらに、約 50 文字の 2 つの文字列の計算に 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;
}