편집 거리에 대해 혼란스러워합니다

Question

편집 거리를 사용하면 아래 코드에서 이미 수행 한 두 문자열 사이의 편집 횟수를 알아야하지만 출력이 예상되는 2 차원 배열을 인쇄하고있는 부분이 있습니다. 같은 : 내가 맞다 경우

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에있는 알고리즘입니다.