To go through the C program / source-code, scroll down to the end of this pageLongest Common SubsequenceA subsequence of a given sequence is the given sequence with just some elements left out (order should be from left-to-right, not necessarily consecutive).. A common sequence of two sequences X and Y, is a subsequence of both X and Y.A longest common subsequence is the one with maximum length. For example, if X = {A,B,C,B,D,A,B} and Y = { B,D,C,A,B,A} then the longest common subsequence is of length 4 and they are {B,C,B,A} and {B,D,A,B}. Finding the longest common subsequence has applications in areas like biology. The longest subsequence (LCS) problem has an optimal substructure property. Thus, the dynamic programming method can be used to solve this problem. Theorem used - Let X =< x1, x2, . . . , xm > and Y =< y1, y2, . . . , yn > be sequences, and let Z =< z1, z2, . . . , zk > be any LCS of X and Y . 1. If xm = yn, then zk = xm = yn and Zk−1 is an LCS of Xm−1 and Yn−1. 2. If xm = yn, then zk = xm implies that Z is an LCS of Xm−1 and Y. 3. If xm = yn, then zk = yn implies that Z is an LCS of X and Yn−1. Complete Tutorial with Examples:C Program Source Code for the Longest Common Subsequence problem#include<stdio.h>
Rough notes about the Algorithm implemented in the code above:
S,T are two strings for which we have to find the longest common sub sequence. Input the two sequences. Now print the longest common subsequence using LongestCommonSubsequence function.
LongestCommonSubsequence function : This function takes the two sequences (S, T) as arguments and returns the longest common subsequence found.
Store the length of both the subsequences. Slength = strlen(S), Tlength = strlen(T). We will Start with the index from 1 for our convenience (avoids handling special cases for negative indices).
Declare common[Slength][Tlength]. Where, common[i][j] represents length of the longest common sequence in S[1..i], T[1..j].
If there are no characters from string S, common[0][i]=0 for all i or if there are no characters from string T, common[i][0]=0 for all i.
Recurrence: for i=1 to Slength
for j=1 to Tlength
common[i][j] = common[i-1][j-1] + 1, if S[i]=T[j]. Else, common[i][j] = max(common[i-1][j],common[i][j-1]). Where max is a function which takes the two
variables as arguments and returns the maximum of them. Return common[Slength][Tlength]. Related Tutorials (common examples of Dynamic Programming):
Some Important Data Structures and Algorithms, at a glance:
| Basic Data Structures and Algorithms Sorting- at a glance
|
Computer Science >