You must answer BOTH questions in SEPERATE java files. 1) Vladimir, a linguist,

Question

You must answer BOTH questions in SEPERATE java files.

1) Vladimir, a linguist, has just discovered a bunch of alien languages (strangely, the languages all use the English alphabet). The aliens were nice enough to provide the same document in multiple alien languages for translation purposes. Before attempting to figure out the meaning of the document, Vladimir decides to run the longest common subsequence algorithm between all the different versions of the document in order to find those which are most similar. Unfortunately, his computer keeps crashing when he tries the two documents below (the programmer didn't thoroughly test the code before releasing it, and therefore is being sued by Vladimir for providing a faulty product). In the meantime Vladimir still needs the solution, help Vladimir out by running the LCS algorithm below.

Documents:

in first language: in ni nat jag dep y togo il ru pur de tuh huh jon stewart

in second language: nat in jag dep huh tuh il de tuh de huh jon y stewart

2) Write out the algorithm for the

Explanation / Answer

/**
** Java Program to implement Longest Common Subsequence Algorithm
**/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/** Class LongestCommonSubsequence **/
public class LongestCommonSubsequence
{
/** function lcs **/
public String lcs(String str1, String str2)
{
int l1 = str1.length();
int l2 = str2.length();

int[][] arr = new int[l1 + 1][l2 + 1];

for (int i = l1 - 1; i >= 0; i--)
{
for (int j = l2 - 1; j >= 0; j--)
{
if (str1.charAt(i) == str2.charAt(j))
arr[i][j] = arr[i + 1][j + 1] + 1;
else
arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]);
}
}

int i = 0, j = 0;
StringBuffer sb = new StringBuffer();
while (i < l1 && j < l2)
{
if (str1.charAt(i) == str2.charAt(j))
{
sb.append(str1.charAt(i));
i++;
j++;
}
else if (arr[i + 1][j] >= arr[i][j + 1])
i++;
else
j++;
}
return sb.toString();
}

/** Main Function **/
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Longest Common Subsequence Algorithm Test ");

System.out.println(" Enter string 1");
String str1 = br.readLine();

System.out.println(" Enter string 2");
String str2 = br.readLine();

LongestCommonSubsequence obj = new LongestCommonSubsequence();
String result = obj.lcs(str1, str2);

System.out.println(" Longest Common Subsequence : "+ result);
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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