Attached is a program lcs1.c which computes the longest common subsequence of two text strings. Recall that the longest common subsequence problem is described in lecture notes Lect 5-2 Dynamic Programming part 2 and in CLRS Section 14.4 (pp. 393-399). If you run it, the program will only give you the length of the longest common subsequence. Rewrite it so that the program will also output the longest common subsequence in addition to its length: String = ABCAABCCABCCBA Length=14 String = BABCCCBBACAA Length=12 LCS: ABCCCACA LCS length = 8 String = ABCBDAB Length=7 String = BDCABA Length=6 LCS: BCBA LCS length = 4

#include  #include  #define DIM 80 #define EMPTY -1 int max(int a, int b); /* Returns max(a,b) */ int strLength(char s[]); /* Returns the length of a char string */ int ** createMemo(int numRow, int numCol); void destroyMemo(int ** memo, int numRow); int lcsRec(char str1[], char str2[] , int ** memo, int len1, int len2) { if (memo[len1][len2]==EMPTY) { if (len1==0 || len2==0) { memo[len1][len2]=0; } else if (str1[len1]==str2[len2]){ memo[len1][len2]=lcsRec(str1,str2,memo,len1-1,len2-1)+1; } else { int temp1=lcsRec(str1,str2,memo,len1-1,len2); int temp2=lcsRec(str1,str2,memo,len1,len2-1); memo[len1][len2]=max(temp1,temp2); } } return memo[len1][len2]; } int lcs(char str1[], char str2[]) { int len1 = strLength(str1); int len2 = strLength(str2); int ** memo = createMemo(len1,len2); for (int i=0; i<=len1; i++) { for (int j=0; j<=len2; j++) { memo[i][j]=EMPTY; } } int result = lcsRec(str1, str2, memo, len1, len2); destroyMemo(memo,len1); return result; } int main() { char str1[]="ABCAABCCABCCBA"; char str2[]="BABCCCBBACAA"; char str3[]="ABCBDAB"; char str4[]="BDCABA"; int length; length = strLength(str1); printf("String = %s Length=%d ",str1,length); length = strLength(str2); printf("String = %s Length=%d ",str2,length); printf("LCS length = %d ",lcs(str1,str2)); printf(" "); length = strLength(str3); printf("String = %s Length=%d ",str3,length); length = strLength(str4); printf("String = %s Length=%d ",str4,length); printf("LCS length = %d ",lcs(str3,str4)); } int ** createMemo(int numRow, int numCol) { int ** memo = (int **) malloc(sizeof(int *)*(numRow+1)); for (int i=0; i<=numRow; i++) { memo[i] = (int *) malloc(sizeof(int)*(numCol+1)); } return memo; } void destroyMemo(int ** memo, int numRow) { for (int i=0; i b) return a; return b; } int strLength(char s[]) { int k=0; for(; s[k]!='\0'; k++); return k; } 

Answer in C please!