Dynamic Programming must be used. Use java, and include a main method that prove

Question

Dynamic Programming must be used. Use java, and include a main method that proves the correctness of the algorithm. Complexity must be O(mn).

Problem 5: (5 + 2 points) Given two sequences of symbols A and B of lengths m and n resepec- tively, design an algorithm for computing the length of the longest possible common subsequence if we are allowed to change at most one element of A. For example, if A = [a, a, b, b, b) and B-a, c, c,b), then the answer is 3, because we can change the second symbol in A and get A = a, c, b, b,b]. After that, the longest common subsequence is [a, c, b]. The complexity of the algorithm has to be O(mn).

Explanation / Answer

/* A Naive recursive implementation of LCS problem in java*/

public class LongestCommonSubsequence

{

int LCS[][];

int lcs( char[] X, char[] Y, int m, int n )

{

int i,j;

LCS=new int[m+1][n+1];

for(i=0;i<m;i++ )

LCS[i][0]=0;

for(j=0;j<n;j++)

LCS[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if (X[i-1] == Y[j-1])

{

LCS[i][j]= LCS[i-1][j-1]+1;

System.out.print(X[i-1]);

}

else

if(LCS[i][j-1]>LCS[i-1][j])

LCS[i][j]=LCS[i][j-1];

else

LCS[i][j]=LCS[i-1][j];

  

return(LCS[i-1][j-1]);

}

/* Utility function to get max of 2 integers */

public static void main(String[] args)

{

LongestCommonSubsequence lcs = new LongestCommonSubsequence();

String s1 = "accb";

String s2 = "acbbb";

char[] X=s1.toCharArray();

char[] Y=s2.toCharArray();

int m = X.length;

int n = Y.length;

  

System.out.println("Length of LCS is" + " " +

lcs.lcs( X, Y, m, n ) );

}

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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