11.26 LAB: Longest common subsequences Overview The longest common substring algorithm is presented elsewhere in this book. The longest common subsequence algorithm is similar. Unlike a substring, a subsequence need not be continuous. Ex: "ARTS" is a subsequence of ALGORITHMS, but is not a substring. A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating the matrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, and left to right across a row. Each entry matrix [R][C] is computed as follows: ⋅ • If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R1] [C1]. If characters do not match, the longest common 。 substring algorithm assigns matrix[R][C] with o ⚫ subsequence algorithm assigns matrix[R][C] with max (matrix [R - 1] [C], matrix [R] [C-1]) Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of trying to access matrix [-1] [-1], 0 is used instead. Sample matrix The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries corresponding to a character match are highlighted. B A N A N A S 111111 011 1 1 1 2 2 1 1 1 --22233 2333 A 0 L A 0 S 0 1 1 2 2 K 0 1 1 A 0 1 1 22 2 2 N 0 1 2 2 3 3 Matching character The largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in the matrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long. Multiple longest common subsequences A pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have three longest common subsequences: "AAA", "AAN", and "AAS". Step 1: Determine how to make the LCS set from the matrix The matrix can be used to build a set of all longest common subsequences. Before writing any code, consider two options for building the LCS set: 1. Build the entire numerical matrix, then traverse the matrix to build the LCS set. 2. Build a matrix of structures that include the numerical entry plus the LCS set. The image below illustrates approach #2. A B B A 0 1 1 1 B {} {"B" } {"B" } {"B" } 1 1 1 2 A {"A"} { "A", "B" } { "A", "B" } {"BA"} 1 1 1 2 A {"A"} {"A", "B" } {"A", "B" } { "AA", "BA"} 1 2 2 2 B { "AB", "BB", {"A"} { "AB"} {"AB", "BB"} "AA", "BA"} Matching character Step 2: Implement the LCSMatrix class The LCSMatrix class is declared in the LCSMatrix.java file. Access LCSMatrix.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The constructor, getEntry(), and getLongest CommonSubsequences() methods must be completed. A field must also be added for the matrix data. Each matrix entry may be an integer or a more complex object, depending on the choice made in step 1. After adding a field for the matrix, complete the methods to satisfy the requirements below. • Constructor: Two lines of code are given to assign the rowCount and columnCount variables to string1's length and string2's length, respectively. The remainder of the method must be implemented to build the longest common subsequence matrix. Use case sensitive character comparisons. Ex: 'a' and 'A' are not equal. ⚫ getEntry(): Returns the numerical entry at the given row and column indices, or 0 if either index is out of bounds. getLongestCommonSubsequences(): Returns a HashSet of strings indicating all longest common subsequences for the two strings passed to the constructor. Step 3: Test in develop mode, then submit Code in LabProgram.java runs several test cases. Every test case tests the HashSet returned from getLongest CommonSubsequences (). Some test cases also test matrix entries returned from getEntry(). Unit tests are similar.
11.26 LAB: Longest common subsequences Overview The longest common substring algorithm is presented elsewhere in this book. The longest common subsequence algorithm is similar. Unlike a substring, a subsequence need not be continuous. Ex: "ARTS" is a subsequence of ALGORITHMS, but is not a substring. A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating the matrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, and left to right across a row. Each entry matrix [R][C] is computed as follows: ⋅ • If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R1] [C1]. If characters do not match, the longest common 。 substring algorithm assigns matrix[R][C] with o ⚫ subsequence algorithm assigns matrix[R][C] with max (matrix [R - 1] [C], matrix [R] [C-1]) Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of trying to access matrix [-1] [-1], 0 is used instead. Sample matrix The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries corresponding to a character match are highlighted. B A N A N A S 111111 011 1 1 1 2 2 1 1 1 --22233 2333 A 0 L A 0 S 0 1 1 2 2 K 0 1 1 A 0 1 1 22 2 2 N 0 1 2 2 3 3 Matching character The largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in the matrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long. Multiple longest common subsequences A pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have three longest common subsequences: "AAA", "AAN", and "AAS". Step 1: Determine how to make the LCS set from the matrix The matrix can be used to build a set of all longest common subsequences. Before writing any code, consider two options for building the LCS set: 1. Build the entire numerical matrix, then traverse the matrix to build the LCS set. 2. Build a matrix of structures that include the numerical entry plus the LCS set. The image below illustrates approach #2. A B B A 0 1 1 1 B {} {"B" } {"B" } {"B" } 1 1 1 2 A {"A"} { "A", "B" } { "A", "B" } {"BA"} 1 1 1 2 A {"A"} {"A", "B" } {"A", "B" } { "AA", "BA"} 1 2 2 2 B { "AB", "BB", {"A"} { "AB"} {"AB", "BB"} "AA", "BA"} Matching character Step 2: Implement the LCSMatrix class The LCSMatrix class is declared in the LCSMatrix.java file. Access LCSMatrix.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. The constructor, getEntry(), and getLongest CommonSubsequences() methods must be completed. A field must also be added for the matrix data. Each matrix entry may be an integer or a more complex object, depending on the choice made in step 1. After adding a field for the matrix, complete the methods to satisfy the requirements below. • Constructor: Two lines of code are given to assign the rowCount and columnCount variables to string1's length and string2's length, respectively. The remainder of the method must be implemented to build the longest common subsequence matrix. Use case sensitive character comparisons. Ex: 'a' and 'A' are not equal. ⚫ getEntry(): Returns the numerical entry at the given row and column indices, or 0 if either index is out of bounds. getLongestCommonSubsequences(): Returns a HashSet of strings indicating all longest common subsequences for the two strings passed to the constructor. Step 3: Test in develop mode, then submit Code in LabProgram.java runs several test cases. Every test case tests the HashSet returned from getLongest CommonSubsequences (). Some test cases also test matrix entries returned from getEntry(). Unit tests are similar.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Write the LCSMatrix.java:
import java.util.*;
// Your code here
// - Import any required additional packages
// - Declare any desired classes to be used by LCSMatrix
public class LCSMatrix {
private int rowCount;
private int columnCount;
//
// Your code here
//
public LCSMatrix(String str1, String str2) {
this.rowCount = (int) str1.length();
this.columnCount = (int) str2.length();
// Your code here
}
// Your code here, if needed
// Returns the number of columns in the matrix, which also equals the length
// of the second string passed to the constructor.
public int getColumnCount() {
return columnCount;
}
// Returns the matrix entry at the specified row and column indices, or 0 if
// either index is out of bounds.
public int getEntry(int rowIndex, int columnIndex) {
// Your code here (remove placeholder line below)
return 0;
}
// Returns the number of rows in the matrix, which also equals the length
// of the first string passed to the constructor.
public int getRowCount() {
return rowCount;
}
// Returns the set of distinct, longest common subsequences between the two
// strings that were passed to the constructor.
public HashSet<String> getLongestCommonSubsequences() {
// Your code here (remove placeholder line below)
return new HashSet<String>();
}
}
![11.26 LAB: Longest common subsequences
Overview
The longest common substring algorithm is presented elsewhere in this book. The longest common subsequence
algorithm is similar. Unlike a substring, a subsequence need not be continuous. Ex: "ARTS" is a subsequence of
ALGORITHMS, but is not a substring.
A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating the
matrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, and
left to right across a row. Each entry matrix [R][C] is computed as follows:
⋅
•
If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R1] [C1].
If characters do not match, the longest common
。 substring algorithm assigns matrix[R][C] with o
⚫ subsequence algorithm assigns matrix[R][C] with max (matrix [R - 1] [C], matrix [R] [C-1])
Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of
trying to access matrix [-1] [-1], 0 is used instead.
Sample matrix
The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries
corresponding to a character match are highlighted.
B A N A N A S
111111
011
1
1 1 2 2
1 1 1
--22233
2333
A
0
L
A
0
S
0 1 1 2 2
K
0 1 1
A
0 1
1
22
2
2
N 0 1 2 2
3
3
Matching character
The largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in the
matrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long.
Multiple longest common subsequences
A pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have three
longest common subsequences: "AAA", "AAN", and "AAS".
Step 1: Determine how to make the LCS set from the matrix
The matrix can be used to build a set of all longest common subsequences. Before writing any code, consider two options
for building the LCS set:
1. Build the entire numerical matrix, then traverse the matrix to build the LCS set.
2. Build a matrix of structures that include the numerical entry plus the LCS set.
The image below illustrates approach #2.
A
B
B
A
0
1
1
1
B
{}
{"B" }
{"B" }
{"B" }
1
1
1
2
A
{"A"}
{ "A", "B" }
{ "A", "B" }
{"BA"}
1
1
1
2
A
{"A"}
{"A", "B" }
{"A", "B" }
{ "AA", "BA"}
1
2
2
2
B
{ "AB", "BB",
{"A"}
{ "AB"}
{"AB", "BB"}
"AA", "BA"}
Matching character](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F1bfda259-7429-4717-b69c-7067c249bba0%2Fc5b18eb4-c15f-48e5-b377-7dc483386b06%2Frnxzwvh_processed.png&w=3840&q=75)
Transcribed Image Text:11.26 LAB: Longest common subsequences
Overview
The longest common substring algorithm is presented elsewhere in this book. The longest common subsequence
algorithm is similar. Unlike a substring, a subsequence need not be continuous. Ex: "ARTS" is a subsequence of
ALGORITHMS, but is not a substring.
A dynamic programming matrix can be used to solve the longest common subsequence problem. Rules for populating the
matrix differ slightly from the longest common substring algorithm. Both algorithms populate rows from top to bottom, and
left to right across a row. Each entry matrix [R][C] is computed as follows:
⋅
•
If characters match, both algorithms assign matrix[R][C] with 1 + matrix[R1] [C1].
If characters do not match, the longest common
。 substring algorithm assigns matrix[R][C] with o
⚫ subsequence algorithm assigns matrix[R][C] with max (matrix [R - 1] [C], matrix [R] [C-1])
Each algorithm uses 0 for out of bounds entries. Ex: When computing matrix[0][0] for a character match, instead of
trying to access matrix [-1] [-1], 0 is used instead.
Sample matrix
The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries
corresponding to a character match are highlighted.
B A N A N A S
111111
011
1
1 1 2 2
1 1 1
--22233
2333
A
0
L
A
0
S
0 1 1 2 2
K
0 1 1
A
0 1
1
22
2
2
N 0 1 2 2
3
3
Matching character
The largest number in the matrix indicates the length of the longest common subsequence. Ex: The largest entry in the
matrix above is 3, so the longest common subsequence between "ALASKAN" and "BANANAS" is 3 characters long.
Multiple longest common subsequences
A pair of strings may have more than one longest common subsequence. Ex: "ALASKAN" and "BANANAS" have three
longest common subsequences: "AAA", "AAN", and "AAS".
Step 1: Determine how to make the LCS set from the matrix
The matrix can be used to build a set of all longest common subsequences. Before writing any code, consider two options
for building the LCS set:
1. Build the entire numerical matrix, then traverse the matrix to build the LCS set.
2. Build a matrix of structures that include the numerical entry plus the LCS set.
The image below illustrates approach #2.
A
B
B
A
0
1
1
1
B
{}
{"B" }
{"B" }
{"B" }
1
1
1
2
A
{"A"}
{ "A", "B" }
{ "A", "B" }
{"BA"}
1
1
1
2
A
{"A"}
{"A", "B" }
{"A", "B" }
{ "AA", "BA"}
1
2
2
2
B
{ "AB", "BB",
{"A"}
{ "AB"}
{"AB", "BB"}
"AA", "BA"}
Matching character
Transcribed Image Text:Step 2: Implement the LCSMatrix class
The LCSMatrix class is declared in the LCSMatrix.java file. Access LCSMatrix.java by clicking on the orange arrow next to
LabProgram.java at the top of the coding window. The constructor, getEntry(), and getLongest CommonSubsequences()
methods must be completed. A field must also be added for the matrix data. Each matrix entry may be an integer or a more
complex object, depending on the choice made in step 1.
After adding a field for the matrix, complete the methods to satisfy the requirements below.
•
Constructor: Two lines of code are given to assign the rowCount and columnCount variables to string1's length and
string2's length, respectively. The remainder of the method must be implemented to build the longest common
subsequence matrix.
Use case sensitive character comparisons. Ex: 'a' and 'A' are not equal.
⚫ getEntry(): Returns the numerical entry at the given row and column indices, or 0 if either index is out of bounds.
getLongestCommonSubsequences(): Returns a HashSet of strings indicating all longest common subsequences for
the two strings passed to the constructor.
Step 3: Test in develop mode, then submit
Code in LabProgram.java runs several test cases. Every test case tests the HashSet returned from
getLongest CommonSubsequences (). Some test cases also test matrix entries returned from getEntry(). Unit tests are
similar.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education