Application: Apply the LCS algorithm on the following instances A = ”xyxxzxyzxy”

Question

Application:

Apply the LCS algorithm on the following instances

A = ”xyxxzxyzxy”

B = “zxzyyzxxyxxz”

Show how to use the resulting tableLto find alltheLongest Common Subsequence

Hint 1:

L [i,j ]=0   , if i=0 or j=0

Hint 2:

L [i,j ]=L[i-1,j-1]+1 , If i>0 , j>0 and ai =bj        

Hint 3 :

L [i,j ]=max{L[i,j-1], L[i-1,j]},   If i>0 , j>0 and ai # bj   

Write it in  Algorithm , and solve it using table by following the hintto help you understand the problem ,,

Explanation / Answer

please rate - thanks hope this helps a sample run ----jGRASP exec: java lcs Enter a string: zzzyzzxyx Enter another string: zzxy zzxy ----jGRASP: operation complete. import java.util.*; public class lcs {public static void main(String[] args)     {String x,y;    int i,j, m,n;       int[][] mat=new int[30][30];       Scanner in=new Scanner(System.in);       System.out.print("Enter a string: ");      x=in.next();       System.out.print("Enter another string:");      y=in.next();      m= x.length();      n=y.length();        for(i=m-1;i>=0;i--)         {for(j=n-1;j>=0;j--)             {if(x.charAt(i)==y.charAt(j))              mat[i][j]=mat[i+1][j+1]++;            else               if(mat[i+1][j]>mat[i][j+1])                      mat[i][j]=mat[i+1][j];                   else                      mat[i][j]=mat[i][j+1];              }         }       i=0;        j=0;       while(i

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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