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 mat rix [R] [C] is computed as follows: a If characters match, both algorithms assign matrix[R][C] with 1 + mat rix[R 1] [C 1]. a If characters do not match, the longest common __ a substring algorithm assigns matrix[R][C] with E! a 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 [ El] [0] for a character match, instead of trying to access matrix [1] [1], D 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. '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 "AA".S 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 Matching character O B { "B" } { "B" } {"B"} 2 A { " A " } { "A", "B" } { "A", "B" } { "BA" } 2 A { "A" } { "A", "B" } { "A", "B" } { "AA", "BA" } 2 2 2 B LCS matrix, with LCS sets in each entry, for [ "A" } strings BAAB and ABBA |"AA", "BA" } Step 2: Implement the LCSMatrix class The LCSMatrix class is declared in the LCSMatrix.h file. Access LCSMatrix.h by clicking on the orange arrow next to main.cpp at the top of the coding window. 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 to string 1's length and string2's length, respectively. The remainder of the function must be implemented to build the longest common subsequence matrix. o 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 an unordered_set 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 main.cpp runs several test cases. Every test case tests the set returned from GetLongestCommonSubsequences(). Some test cases also test matrix entries returned from GetEntry(). Unit tests are similar. Ensure that all tests pass in develop mode before submitting code.Program timed out Your output FAIL: "BAA" and "ABBA" Expected matrix: [01 1 1 ] [1 1 1 2 ] [1 1 12 ] Actual matrix : [01 1 1 ] [1 1 1 2 ] [1 1 12 ] Expected LCS set: { "BA", "AA" } Actual LCS set: { "AB", "BC", "AC"} FAIL: "function" and "method" Expected matrix: [0 0 0 0 0 0 ] [ 0 0 0 0 0 0 ] [0 0 0 0 0 0 ] [ 0 0 0 0 0 0 ] [0 01 1 1 1 ] [0 01 1 1 1 ] [0 01 1 2 2 ] [0 01 1 2 2 ] Actual matrix: [ 0 0 0 0 0 0 ] [0 0 0 0 0 0 ] [0 0 0 0 0 0 ] [0 0 0 0 0 0 ] [001 1 1 1 ] Test feedback [001 1 1 1 ] [0 01 1 2 2 ] [0 01 1 2 2 ] Expected LCS set: {"to" Actual LCS set: [ "GH", "FH", "EH", "FG", "EG"} FAIL: "BAAB" and "ABB" Expected matrix : [01 1 [1 1 1] [1 1 1 ] [ 1 2 2 ] Actual matrix : [01 1] [1 1 1] [1 1 1 ] [ 1 2 2 ] Expected LCS set: { "BB", "AB"} Actual LCS set: { "AD", "CD", "BD" } FAIL: "min = (x y) ? x : y" Expected LCS set: ["m = (x y) ? x : y"} Actual LCS set: { "CDEFGHKLMNOPQRSTUV", "BDEFGHKLMNOPQRSTUV", "ADEFGHKLMNOPQFFAIL : "SLEEPING" and "CAT" Expected LCS set: { } Actual LCS set: }