Question

Show the longest common subsequence array \(L\) for the two strings \\[ \begin{aligned} X &=" \text { skullandbones " } \\ Y &=\text { "Iullabybabies" } \end{aligned} \\] What is a longest common subsequence between these strings?

Short answer

\(\text{ulab}\) is a longest common subsequence.

Step-by-step solution

- Initialize the L Table

Create a 2D array \( L \) with dimensions (length of \(X\) + 1) by (length of \(Y\) + 1), initialized to zeros. The table helps in storing the lengths of longest common subsequences.

- Fill the L Table

Fill the 2D array \( L \) based on the relationships between characters in \( X \) and \( Y \). If \(X[i-1] == Y[j-1]\), then \(L[i][j] = L[i-1][j-1] + 1\). Otherwise, \(L[i][j] = \text{max}(L[i-1][j], L[i][j-1])\).

- Trace Back to Find the Sequence

Starting from \( L[length(X)][length(Y)] \), trace back to find the longest common subsequence by following the rules in the table.

- Form the Longest Common Subsequence

Form the longest common subsequence by appending the characters when a match is found during the trace-back process.

Key concepts

dynamic programming

Dynamic programming (DP) is a method used to break down complex problems into simpler subproblems. It does this by storing the results of these subproblems to avoid redundant calculations and improve efficiency. In the context of finding the longest common subsequence (LCS), DP helps by breaking the problem down into smaller segments and solving each segment while remembering its solution. This way, once part of the problem is solved, it doesn't have to be solved again if it appears in another segment. Utilizing dynamic programming saves time, especially for problems with overlapping subproblems and optimal substructure, like LCS.

To implement DP for LCS, we create a 2D array to store solutions to subproblems. Each cell in the table represents the length of the LCS up to the corresponding positions in the input strings.

2D array

A 2D array is a data structure that uses two indices to access elements arranged in rows and columns. In the LCS problem, we use a 2D array to store the lengths of the longest subsequences for substrings of the given strings. The dimensions of the array are (length of string X + 1) by (length of string Y + 1). This accounts for every possible substring length of both strings, including the empty substring.

Here's how to initialize and fill this table:

• Initialize the first row and the first column to zeros. This represents comparing against an empty substring.
• For each character of the two strings, compare them. If they match, increment the value from the diagonal cell (top-left) by 1. If they don't match, take the maximum value between the left cell and the top cell.

This step-by-step approach ensures every possible combination of substrings is considered, leading to the final answer being stored in the cell representing full lengths of both strings.

trace back method

The trace back method is a crucial step in dynamic programming problems like the LCS. Once we have filled our 2D array with lengths of the longest common subsequences, we need to figure out the actual sequence.

Here's how the trace back works:

• Start from the bottom-right cell of the filled 2D array.
• If the characters corresponding to the current cell in the strings match, this character is part of the LCS. Move diagonally up-left in the array.
• If the characters do not match, move in the direction of the larger value between the top cell or the left cell.

Repeat these steps until reaching the top-left cell of the array.

By following this path, the characters from the LCS are collected in reverse order, which should be reversed to get the correct sequence. The trace back method helps in constructing the exact LCS efficiently.