Step 1: Input and Output

Write a program to read in the two strings from standard input and print them to standard output. Also print their lengths.

  • Declare character arrays, say x[] and y[] to store the two strings. Make sure that each string can store up to 10,000 characters.

  • Use the scanf() function with the "%s" formatting flag to read in each string.

  • Compute and store the lengths, say M and N, of the two strings. Consider using the string library function strlen().

  • Print the strings and their lengths to standard output using printf(). Throroughly debug your program before continuing.

    • Step 2: Optimal value matrix

    Allocate and initialize a two dimension array, say opt[0..M][0..N] to store the edit distances of the subproblems.

  • You may assume M and N are at most 10,000. Declare opt[][] as a global variable; otherwise you will likely run out of memory. Typically, global varaibles are allocated on the heap, while local variables are alloated on the stack. Most systems limit the stack space to some small quantity, and your program may crash without providing a descriptive error message.

  • Write a function to initialize opt[0..M-1][0..N-1] to some sentinel value, say -1 (or better use the macro #define UNDEFINED -1). . Initialize opt[M][0..N] and opt[0..M][N] according to the base case of the edit-distance recurrence.

  • Write a helper function to print out the contents of opt[][] to standard output.

  • Update main() to initialize opt[][] and print it out. Throroughly debug your program before continuing.

    • Step 3: Computing the optimal value matrix

    Read Sedgewick 5.3 first. Now, it's time to write the main recursive function.

    Step 4: Computing the optimal decision matrix

    Add a second matrix, say sol[][]. Modify the initialization and recursive solution functions to comptue the optimal decision along with the optimal values.

    Step 5: Printing the alignment

    Wrtie a function, say printAlignment() to print the optimal alignment. We recommend a single while loop.

    Written by Kevin Wayne