Print longest common subsequence string of two string

The longest subsequence problem (LCS) is the problem in which we need to find the longest subsequence present in two sequences. In this case, characters doesn’t require to be in consecutive places.

For eg:

LCS for sequence “ABCDFG” and “ABCGDFG” is “ABCDFG” and its length is 6.

For calculating longest common subsequence length we can use recursion or dynamic programming, here we are going to see how to find the longest common subsequence string.

For finding out longest common subsequence we are going to use Dynamic Programming method here in which we are going to create a 2D array of size LCS [len_a + 1] [len_b + 1] where,

“len_a” = string length of 1st string.
“len_b” = string length of 2nd string.

This LCS 2D array will contain the longest subsequence value if strings are of its corresponding string lengths which means,

LCS [i] [j] = x (when 1st string is of “i” length and 2nd string is of “j” length.)

Let’s take an example to make it more clear:

Let’s assume 1st string is “ABCGDFG” and 2nd string is “ABCDFG“. Let’s see how the 2D array will look like (just ignore the coloured part for now).

For printing the LCS string we have to start from the end (in this case LCS [6][7]). Now we have to traverse this 2D as follows:

• If character matches at any position then add that character in LCS string, means if ( String_1 [7] == String_2[6]) then add that to LCS string.
• If characters doesn’t match then traverse to “Max (LCS [i-1][j], LCS[i][j-1])” Notice how we have moved for position (3,4) to (3,3) in above 2D array.

First check out for the solution to find Longest Subsequence String length. Now, Let’s check out the code for doing this.

void findLongestSubsequence (char *str_a, char *str_b, int len_a, int len_b)
{
	int i = len_a;
	int j = len_b;
	int lcs_str_length = LCS[len_a][len_b];
	char lcs_str[lcs_str_length + 1];

	lcs_str [lcs_str_length] = '\0';
	lcs_str_length;
	while (i > 0 && j > 0)
	{
		if (str_a[i-1] == str_b[j-1])
		{
			/* Add character to LCS string */
			lcs_str [lcs_str_length - 1] = str_a[i-1];
			lcs_str_length--;
			i--;
			j--;
		}
		else if (LCS[i-1][j] > LCS[i][j-1])
		{
			i--; /* going for matching character */
		}
		else
		{
			j--; /* going for matching character */
		}
	}
	printf ("LCS string is : %s \n", lcs_str);
}

Let’s see the output of the above program (For calculating LCS check here).

enter string a 
abcdfghjklijhy
enter string b 
acbkcdfghopjkxlijhy
LCS using dp 14, time taken: 8  
LCS string is : abcdfghjklijhy 


/* Another example */

enter string a 
abcgdfg
enter string b 
abcdfg
LCS using dp 14, time taken: 4  
LCS string is : abcdfg