HW3_Levenstein

#include <cstdio>
#include <cstdlib>
#include <cstring>

int min(int a, int b, int c)
{
    if (a < b && a < c)
        return a;
    else if (b < c)
        return b;
    else
        return c;
}

int main()
{
    int n = 0, m = 0;
    scanf("%d", &n);
    scanf("%d", &m);
    char* str1 = (char*)malloc((n + 1)*sizeof(char));
    scanf("%s", str1);
    str1[n] = '0';
    char* str2 = (char*)malloc((m + 1)*sizeof(char));
    scanf("%s", str2);
    str2[m] = '0';
    int** matrix = (int**)malloc((m + 1)*sizeof(int*));
    for (int i = 0; i <= m; ++i)
    {
        matrix[i] = (int*)malloc((n + 1)*sizeof(int));
        if (!i)
        {
            for (int j = 0; j <= n; ++j)
            {
                matrix[i][j] = j;
                printf("%d ", matrix[i][j]);
            }
        }
        else
        {
            printf("\n");
            matrix[i][0] = i;
            printf("%d ", matrix[i][0]);
            for (int j = 1; j <= n; ++j)
            {
                if (str1[j-1] == str2[i-1])
                    matrix[i][j] = min(matrix[i][j - 1] + 1, matrix[i - 1][j] + 1, matrix[i - 1][j - 1]);
                else
                    matrix[i][j] = min(matrix[i][j - 1] + 1, matrix[i - 1][j] + 1, matrix[i - 1][j - 1] + 1);
                printf("%d ", matrix[i][j]);
            }
        }
    }
    printf("\n");
    printf("%d\n", matrix[m][n]);
    return 0;
}