The code below already has an implementation that uses recursion to find the minimum edit distance but this implementation has an exponential runtime compared to the edit distance, and so is much too inefficient for all but the simplest test cases. Use a dynamic programming algorithm to calculate the Levenshtein edit distance using matrix, or an array of arrays, to record intermediate calculations and make this algorithm efficient. **please try it with bigger strinngs

code to edit:

#include

#include

#include

size_t min ( size_t x, size_t y ) {

return x

}

size_t levenshtein_recursive ( char* source, char* target ) {

// printf( "source=%s ", source );

// printf( "target=%s ", target );

if (strlen(source)==0) return strlen(target);

else if (strlen(target)==0) return strlen(source);

else if (source[0]==target[0]) return levenshtein_recursive (source+1, target+1);

else {

size_t ins = levenshtein_recursive (source+1, target );

size_t del = levenshtein_recursive (source, target+1);

size_t sub = levenshtein_recursive (source+1, target+1);

return 1 + min( min(ins,del), sub );

}

}

int main(int argc, char* argv[])

{

FILE* inputFile = fopen(argv[1], "r");

if (!inputFile) {

perror("fopen failed");

return EXIT_FAILURE;

}

char source[32];

char target[32];

fscanf (inputFile, "%s %s", source, target);

printf("%ld ", levenshtein_recursive ( source, target ));

return EXIT_SUCCESS;

}