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 $($LCS$)$ 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$[$R $-1][$C $-1].$

If characters do not match, the longest common $\_\_\_\_\_.$

substring algorithm assigns matrix$[$R$][$C$]$ with $0$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, $0$ is used instead of trying to access matrix$[-1][-1].$

Sample matrix

The image below shows the longest common subsequence matrix for strings "ALASKAN" and "BANANAS". Entries corresponding to a character match are highlighted.

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:

Build the entire numerical matrix, then traverse the matrix to build the LCS set.

Build a matrix of structures that include the numerical entry plus the LCS set.

The figure below illustrates approach #$2.$

Step $2$: Implement the LCSMatrix class

The LCSMatrix class is declared in the LCSMatrix.h file. The constructor, GetEntry$(),$ and GetLongestCommonSubsequences$()$ member functions must be completed. A member variable 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 member variable for the matrix, complete the member functions to satisfy the requirements below.

Constructor: Two lines of code are given to assign the rowCount and columnCount variables with string$1\text{'}$s length and string$2\text{'}$s length, respectively. The remainder of the function must be implemented to build the longest common subsequence matrix.

Use case$-$sensitive character comparisons. Ex: $\text{'}$a$\text{'}$ and $\text{'}$A$\text{'}$ 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 an unordered$\_$set of strings indicating all longest common subsequences for the two strings passed to the constructor.

Step $3$: Test code, then submit

Code in main.cpp runs several test cases. Each tests the set returned from GetLongestCommonSubsequences$().$ Some test cases also check matrix entries returned from GetEntry$().$ Ensure that all tests in main.cpp pass before submitting code for grading.

#ifndef LCSMATRIX$\_$H

#define LCSMATRIX$\_$H

#include

#include

$//$ TODO: Type your code here

$//-$ Include any required additional headers

$//-$ Declare any desired classes$/$structs to be used by LCSMatrix

class LCSMatrix $\{$

private:

$$int rowCount;

$$int columnCount;

$//$

$//$ TODO: Type your code here

$//$

public:

$$LCSMatrix$($std::string& str$1,$ std::string& str$2)\{$

$$ this$->$rowCount $=($int$)$ str$1.$length$()$;

$$ this$->$columnCount $=($int$)$ str$2.$length$()$;

$$

$//$ TODO: Type your code here

$\}$

$$

$//$ Your code here, if needed

$//-$ If matrix data is dynamically allocated, add destructor

$$

$//$ Returns the number of columns in the matrix, which also equals the length

$//$ of the second string passed to the constructor.

$$int GetColumnCount$()\{$

$$ return columnCount;

$\}$

$$

$//$ Returns the matrix entry at the specified row and column indices, or $0$ if

$//$ either index is out of bounds.

$$int GetEntry$($int rowIndex, int columnIndex$)\{$

$//$ TODO: Type 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.

$$int GetRowCount$()\{$

$$ return rowCount;

$\}$

$$

$//$ Returns the set of distinct, longest common subsequences between the two

$//$ strings that were passed to the constructor.

$$std::unordered$\_$set GetLongestCommonSubsequences$()\{$

$//$ TODO: Type your code here $($remove placeholder line below$)$

$$ return std::unordered$\_$set$()$;

$\}$

$\}$;

#endif