#include <stdio.h>
#include <string.h>

#define MAX_LEN 100

int lowest(int values[], int n) { /* 整数の配列の中から最小値を返す */
    int lowest = values[0];
    int i = 0;
    for (i = 1; i < n; i++) {
        if (values[i] < lowest) {
            lowest = values[i];
        }
    }
    return lowest;
}

int eddist_iter(char *str1, char *str2, int len1, int len2) {
    /* （再帰呼び出しを使わずに）編集距離（レーベンシュタイン距離）を計算する関数
    str1, str2 は対象の文字列
    len1, len2 は文字列の長さ */
    int matrix[MAX_LEN+1][MAX_LEN+1];
    int i, j;
    int opt[3];

    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            /* str1の終端に到達した場合、str2の残りの文字数を返す */
            if (i == 0) {
                matrix[i][j] = j;
            /* str2の終端に到達した場合、str1の残りの文字数を返す */
            } else if (j == 0) {
                matrix[i][j] = i;
            /* 両方の文字列が対象の位置に同じ文字を持つ場合、編集距離は増えない */
            } else if (str1[i-1] == str2[j-1]) {
                matrix[i][j] = matrix[i-1][j-1];
            /* 対象の位置にある文字が異なる場合、可能な編集を全て検討し
            最小値を求める */
            } else {
                opt[0] = matrix[i][j-1]; /* str1に1文字を挿入することと同じ */
                opt[1] = matrix[i-1][j]; /* str1から1文字を削除することと同じ */
                opt[2] = matrix[i-1][j-1]; /* str1の1文字を置き換えることと同じ */
                matrix[i][j] = 1 + lowest(opt, 3);
            }
        }
    }
    /* 処理が終わったら表の最後のセルに最小距離が入っているのでそれを返す */
    return matrix[len1][len2];
}

int main()
{
    int dist;
    char str1[] = "programming is fun!";
    char str2[] = "promising young man";
    dist = eddist_iter(str1, str2, strlen(str1), strlen(str2));
    printf("Edit distance: %d\n", dist);
}