FYI I have received 3 incorrect answers from chegg already! Please post correct
ID: 3716507 • Letter: F
Question
FYI I have received 3 incorrect answers from chegg already! Please post correct answer.
(PROGRAM IN JAVA)
Given 3 Strings, find the length of the longest common subsequence.
Input- The input file NEEDS to be CALLED input2.txt and be in the same directory as the java and class files. The file will contain 3 lines and each line will be one of the three strings.
Output- A number N where the length of the longest common subsequence. This value should be calculated in POLYNOMIAL time using DYNAMIC PROGRAMMING.
Examples: If the input was
aaaaaxbbbbb
bbbbbxccccc
cccccxddddd
then the output would be 1, because the longest common substring in x.
Example 2: if the input file was
ccabacbaabad
dababccaaba
ccddababaaba
then the output would be 8, because the longest common substring is ababaaba.
THE PROGRAM MUST BE IN JAVA AND…..COMPILE WITH THE COMMAND javac *.java and run with command java Project2.
MUST USE DYNAMIC PROGRAMMING.
Explanation / Answer
------------------------strings.txt----------------
ccabacbaabad
dababccaaba
ccddababaaba
-----------------Code------------------
import java.util.*;
import java.io.*;
public class Project2 {
public static void main(String args[]){
String str1 = "";
String str2 = "";
String str3 = "";
try{
String fileName = "strings.txt";
FileInputStream dataStream = new FileInputStream(fileName);
Scanner fileIn = new Scanner(dataStream);
str1 = fileIn.nextLine();
str2 = fileIn.nextLine();
str3 = fileIn.nextLine();
}catch(Exception e){
System.out.println("Cannot open file named '" + args[0] + "'");
}
int len1 = str1.length();
int len2 = str2.length();
int len3 = str3.length();
System.out.println(lcs(str1,str2,str3,len1,len2,len3));
}
/* Returns length of LCS for string X, Y, Z ending at
m,n,o lengths respectively
Initially called with actual lengths of string
*/
public static int lcs(String X, String Y, String Z, int m, int n, int o){
int[][][] L = new int[m+1][n+1][o+1];
/* Following steps build L[m+1][n+1][o+1] in
bottom up fashion. Note that L[i][j][k]
contains length of LCS of X[0..i-1] and
Y[0..j-1] and Z[0.....k-1]*/
for (int i=0; i<=m; i++){
for (int j=0; j<=n; j++){
for (int k=0; k<=o; k++){
if (i == 0 || j == 0||k==0){
// Filling array for base case
L[i][j][k] = 0;
}else if (X.charAt(i - 1) == Y.charAt(j - 1)
&& X.charAt(i - 1)==Z.charAt(k - 1)){
L[i][j][k] = L[i-1][j-1][k-1] + 1;
}else{
L[i][j][k] = Math.max(Math.max(L[i-1][j][k],L[i][j-1][k]),L[i][j][k-1]);
}
}
}
}
/* L[m][n][o] contains length of LCS for actual strings*/
return L[m][n][o];
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.