Coders Packet

Length of Longest common subsequence using C++

By Akshay Sai Reddy Kondu

This program is built in C++ which finds the length of the longest common subsequence among two given input strings. The project is made by using Dynamic Programming methods.

The main aim of our project is to find the length of common subsequences, using Dynamic Programming.

Subsequences of a given string: Suppose the given string is, "xayb", then the possible subsequences are x, a, y, b, xa, xy, xb, ay, ab, by, xay, xab, xyb, ayb, xayb. Observe that any subsequence follows the same relative order as of the given string.

Now, given two strings, we have to find out the longest common subsequence and print its length. For, this we use dynamic programming where we tabulate the lengths of common subsequences which processed in before iterations so that we can avoid recomputation of them again if they come across again in the next iterations.

Algorithm/ Pseuso code:

1. Create a 2D array, length[m+1][n+1], where m and n are the lengths of the two input strings, so that length[i][j] stores length of longest common subsequence s1[0....i-1] and s2[0....j-1], where s1 and s2 are the input strings.

2. Iterate through both the strings character-wise, using two nested for loops.

3. Make the first row and first column of the length array zero, since length[0][j] or length[i][0] has no meaning according to our assumption above.

4. If a common character is found, (s1[i]==s2[j]), then length[i][j] = length[i - 1][j - 1] + 1,

5. Else, length[i][j] = max(length[i - 1][j], length[i][j - 1]),

6. Now our result (length of longest common subsequence) is nothing but, length[m][n].

So, by using dynamic programming we reduced the time complexity to O(m*n), where m and n are the lengths of two strings.



Download Complete Code


No comments yet