The Longest Common Subsequence (LCS) of two strings: Sa = sa1 sa2 ... sam and Sb

Question

The Longest Common Subsequence (LCS) of two strings: Sa = sa1 sa2 ... sam and Sb = sb1 sb2 ... sbn is a string Sc = LCS(Sa, Sb) = sc1 sc2 ... scq such that Sc is a subsequence of Sa, and Sc is a subsequence of Sb, and for any other common subsequence Sc' of Sa and Sb, length(Sc) >= length(Sc'). It is possible to compute the length of an LCS using Dynamic Programming. (a) give a recurrence equation for computing M(Prefix(Sa, i), Prefix(Sb, j)) which is defined as the length of a longest common subsequence of Prefix(Sa, i) and Prefix(Sb, j). Here Prefix(S, k) is defined as the string consisting of the first k characters of S. (b) Draw the 2D array of values for M(Prefix(Sa, i), Prefix(Sb, j)) for the following pair of strings. Sa = A L K W A R I Z M I Sb = A L G O R I T H M (c) Draw a backtrace on the array that shows how to recover LCS(Sa, Sb) from the M array. Circle the entries of the array M that correspond to one particular LCS.

Explanation / Answer

Please rate :) #include #include void print_lcs(char b[10][10],int x[10],int i,int j) { if(i==0||j==0) { return; } if(b[i][j]=='d') { print_lcs(b,x,i-1,j-1); printf("%d",x[i-1]); } else { if(b[i][j]=='u') { print_lcs(b,x,i-1,j); } else { print_lcs(b,x,i,j-1); } } } void main() { int m,n,i,j,c[10][10],x[10],y[10]; char b[10][10]; clrscr(); printf(" Enter the length of first array: "); scanf("%d",&m); printf(" Enter %d elements: ",m); for(i=0;i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.