Question: In this project, you will implement the dynamic programming-based solution to find the longest co……

package regex;

import java.util.Scanner;
import java.lang.*;
import static java.lang.Integer.max;

/**
*
* @author prathmesh
*/
public class chegg {

/**
* @param args the command line arguments
*/
String x,y,ans=””,ans2=””;
chegg(String a,String b){
this.x = a;
this.y = b;
}
int recur(String x,String y,int i,int j){
if(i==0 || j==0){
return 0;
}
if(x.charAt(i-1) == y.charAt(j-1)){
dp[i][j] = 1 + recur(x,y,i-1,j-1);
}
else{
dp[i][j] = max(recur(x,y,i-1,j),recur(x,y,i,j-1));
}
return dp[i][j];

}
void lcs(){
for(int i=0;i<100;i++){
for(int j=0;j<100;j++){
dp[i][j] = 0;
}
}
recur(x,y,x.length(),y.length());
}
void printdp(){

for(int i=0;i<=x.length();i++){
for(int j=0;j<=y.length();j++){
System.out.print( dp[i][j]+ ” “);

}
System.out.println(“”);
}
recur(x,y,x.length(),y.length());
}
String printlcs(){
int i=x.length();
int j=y.length();

while(i>0 && j>0){
if(x.charAt(i-1)==y.charAt(j-1)){
ans += x.charAt(i-1);
i–;j–;
}
else if(dp[i-1][j] > dp[i][j-1]){
i–;
}
else{
j–;
}
}
// As the LCS string is in reverse;
for(i=ans.length()-1;i>=0;i–){
ans2 += ans.charAt(i);
}
return ans2;
}
int dp[][] = new int[100][100];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String x = input.next();
String y = input.next();
chegg c = new chegg(x,y);
c.lcs();
System.out.println( “Longest subsequence : ” + c.printlcs());
c.printdp();

}

}

As you can see, there are mainly three functions”-

1)lcs

It calculates and builds the dynamic programming table, also initilizes all the values to 0.

2) printlcs

It traverses the table and creates the answer by the entries in the DP table.

We start from the bottom and traverse up by going towards the direction which has a higher value.

3)printdp

To print the dp table.

Note: Final alignment can be worked out simply by looking at the strings manually