Путаница о расстоянии редактирования

Question

Используя расстояние редактирования, я должен найти, сколько изменений между двумя строками, которые я уже сделал в моем коде ниже, но часть, на которую я застрял, - это печатать 2d-массив, который, как предполагается, должен выглядеть как это:

int editdistance(char *s, int ls, char *t, int lt) 
{ 
    int a, b, c; 
    if (!ls) return lt; 

    if (!lt) return ls; 

    if (s[ls] == t[ls]) 
      return editdistance(s, ls - 1, t, lt - 1); 
    a = editdistance(s, ls - 1, t, lt - 1); 
    b = editdistance(s, ls,  t, lt - 1); 
    c = editdistance(s, ls - 1, t, lt ); 

    if (a > b) a = b; 
    if (a > c) a = c; 

    return a + 1; 
} 

int main() 
{ 
char s1[100]; 
char s2[100]; 
printf("first: \n"); 
scanf("%s",s1); 
printf("second: \n"); 
scanf("%s",s2); 

printf("edit distance: %d\n", editdistance(s1, strlen(s1), s2, strlen(s2))); 

    return 0; 
} 

Answer 1

Если я прав, вы ищете Levenshtein distance. это алгоритм в Dynamic programming.