Question

Write a pseudocode description of the printLCS () algorithm, which prints the longest common subsequence of two strings x and y. Your algorithm should take as input the completed ïïcs Π integer array of longest common subsequence lengths, and the two strings x and y. (So, you do not have the path[] [] array - see Lecture 19, slides 100 and 101.) Your algorithm must return the specific string corresponding the length found in 1lcs [n] [m] and it should run in O(n + m) time, where n is the length of x and m is the length of y

Answer 1

Following is algorithm to print the LCS. It uses the same 2D table L[][].

There are two strings X and Y
length of X is m
length of Y is n
1) Construct L[m+1][n+1] using the steps of finding the matrix for length of lcs.

2) The value L[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0, to end the char array.).

2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]

   a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.

   b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

Code to print the longest common sub sequence of two Strings X and Y.

#this method returns the matrix of lcs
def lcs(X, Y, m, n):
L = [[0 for x in range(n+1)] for x in range(m+1)]
  
# Following steps build L[m+1][n+1] in bottom up fashion. Note
# that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])

return L

#this method prints the LCS.
def print_lcs(L, X, Y):
  
m = len(X)
n = len(Y)
# Following code is used to print LCS
index = L[m][n]
  
# Create a character array to store the lcs string
lcs = [""] * (index+1)
lcs[index] = ""
  
# Start from the right-most-bottom-most corner and
# one by one store characters in lcs[]
i = m
j = n
while i > 0 and j > 0:
  
# If current character in X[] and Y are same, then
# current character is part of LCS
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i-=1
j-=1
index-=1
  
# If not same, then find the larger of two and
# go in the direction of larger value
elif L[i-1][j] > L[i][j-1]:
i-=1
else:
j-=1
  
print("LCS of " + X + " and " + Y + " is " + "".join(lcs))
  
# Driver program
X = "Shashank Shukla"
Y = "Surbhi Sharma"
m = len(X)
n = len(Y)

L = lcs(X, Y, m, n)
print_lcs(L, X, Y)