Skip to content

Instantly share code, notes, and snippets.

@tinylamb

tinylamb/EditDistance.c

Created March 17, 2014 08:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tinylamb/9595916 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tinylamb/9595916 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tinylamb created this gist Mar 17, 2014.
    57 changes: 57 additions & 0 deletions EditDistance.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,57 @@
    /*
    * =========================================================
    * 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;
    }