#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(char *str1, char *str2, int pos1, int pos2, int memo[MAX_LEN][MAX_LEN]) {
    /* 編集距離（レーベンシュタイン距離）を計算する関数
    str1, str2 は対象の文字列
    pos1, pos2 は現在見ている文字の位置（添え字+1）
    memo 既に計算した結果を保管するための配列 */
    int opt[3];
    int dist;
    if (memo[pos1][pos2] > 0) {
        return memo[pos1][pos2];
    } else if (pos1 == 0) { /* str1の終わりに到達した場合、str2の残りの文字数を返す */
        return pos2;
    } else if (pos2 == 0) { /* str2の終わりに到達した場合、str1の残りの文字数を返す */
        return pos1;
    } else if (str1[pos1-1] == str2[pos2-1]) { /* 両方の文字列が対象の位置に同じ文字を持つ場合、次の位置に移動する */
        return eddist(str1, str2, pos1-1, pos2-1, memo);
    } else {  
        opt[0] = eddist(str1, str2, pos1-1, pos2, memo); /* str1から1文字を削除することと同じ */
        opt[1] = eddist(str1, str2, pos1, pos2-1, memo); /* str1に1文字を挿入することと同じ */
        opt[2] = eddist(str1, str2, pos1-1, pos2-1, memo); /* str1の1文字を置き換えることと同じ */
        dist = 1 + lowest(opt, 3);
        memo[pos1][pos2] = dist;
        return dist;
    }
}

int main()
{
    int dist;
    char str1[] = "programming is fun!";
    char str2[] = "promising young man";
    int memo[MAX_LEN][MAX_LEN] = {0}; /* 全ての要素を 0 に初期化 */
    dist = eddist(str1, str2, strlen(str1), strlen(str2), memo);
    printf("Edit distance: %d\n", dist);
}