/*
 * =========================================================
 *       Filename:  EditDistance.c
 *    Description:  动态规划求编辑距离
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
int Length(char *s);
int EditDistance(char *s , char *t);
int Min(int x,int y,int z);
int main(){
    char *s="cats";
    char *t="fast";
    int dis=EditDistance(s,t);
    printf("dis between %s and %s is %d\n",s,t,dis);
}

int Length(char *s){
    int l=0;
    while( *s != '\0'){
        ++s;
        ++l;
    }
    return l;
}
int Min(int x,int y,int z){
    int temp = (x>y)?y:x;//求最小 不是最大
    return (temp>z)?z:temp;
}
int EditDistance(char *s , char *t){
    int len_s = Length(s);
    int len_t = Length(t);
//    printf("%d %d\n",len_s,len_t);
    //动态二维数组空间分配
    int **m , i ,j;
    m = malloc((len_s + 1) * sizeof(int *));
    for (i=0;i<=len_s;i++)
        m[i] = malloc((len_t + 1) * sizeof(int));
    for (i=0;i <=len_s;i++){
        m[i][0] = i;
    }
//    printf("done\n");
    for (j=0;j<= len_t;j++){
        m[0][j] =j;
    }
//    printf("done\n");
    for (i=1;i<=len_s;i++)
        for (j=1;j<=len_t;j++){
            m[i][j]=Min( m[i-1][j-1]+ ((s[i-1] == t[j-1])?0:1) ,m[i-1][j] + 1,m[i][j-1] +1);
        }
    printf("now i is %d j is %d\n",i,j);
//    int dis =m[i][j];你说为什么会segmentation fault
    int dis =m[len_s][len_t];
    return dis;
}