A subsequence is a group of characters return from a string which may not be contiguous but nevertheless taken in order from the given string ‘x’. The no of characters in the subsequence define the length of the subsequence. Given two strings ‘x’ and ‘y’  of length ‘m’ and ‘n’ respectively, A subsequence i.e. common  to both ‘x’ and ‘y’ is known as common subsequence of ‘x’ and ‘y’ . The longest common subsequence (LCS) problem is to find common subsequence of largest length of given two strings ‘x’ and ‘y’ .

We are given two sequences x[m] and y[n] of lengths m and n respectively.

We wish to find the length of the LCS  of x[m] and y[n] as L(m,n), where an incomplete recursive definition for the function L(i,j) to compute the length of The LCS of x[m] and y[n] is given below:

L[i,j] = 0, if either i=0 or j=0
       = expr1, if i,j > 0 and x[i] = y[j]
       = expr2, if i,j > 0 and x[i] != y[j]