Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L}

To find the Longest Common Subsequence (LCS) of two given sequences A and B, we can use dynamic programming.

Step 1: Create a matrix with dimensions (m+1) x (n+1), where m is the length of sequence A and n is the length of sequence B. Initialize all the cells of the matrix to 0.

Step 2: Iterate through each cell of the matrix, starting from the top-left corner. For each cell (i, j), do the following:

• If the characters at A[i-1] and B[j-1] are the same, set the value of the current cell to the value of the cell diagonally above and to the left (i.e., matrix[i-1][j-1]) plus 1.

• Otherwise, set the value of the current cell to the maximum of the value in the cell above (i.e., matrix[i-1][j]) and the value in the cell to the left (i.e., matrix[i][j-1]).

Step 3: After iterating through all the cells, the bottom-right cell of the matrix (i.e., matrix[m][n]) will contain the length of the LCS.

Step 4: To find the actual LCS, start from the bottom-right cell and backtrack through the matrix. If the characters at A[i-1] and B[j-1] are the same, add that character to the LCS and move diagonally up and to the left. Otherwise, move either up or to the left, depending on which adjacent cell has a higher value.

In this case, the LCS of A={K,A,N,D,L,A,P} and B={A,N,D,L} is "ANDL".