Longest Common Subsequence166 views
function LCS(s1,s2){
var lcs=[], // final lcs will be stored in this
m=[], // two dim array to store max length of common sub-sequences
b=[], // two dim array to remember decisions made which will be traced back to generate solution
CONST_EQUAL=1,CONST_J=0,CONST_I=2, //some constants
i,j; // loop counters
for(i=0;i<=s1.length;i++){
m[i] = [];
b[i] =[];
for(j=0;j<=s2.length;j++){
if(i===0||j===0){
// LCS(Xi,phi) = LCS(phi,Yj) = LCS(phi,phi) = phi
m[i][j] = 0;
} else if(s1[i-1]===s2[j-1]){
// LCS(Xi,Yj) = (LCS(Xi-1,Yj-1),Xi) if Xi=Yj
m[i][j] = m[i-1][j-1]+1;
// remember that s1[i-1]==s2[j-1]
b[i][j]=CONST_EQUAL;
// LCS(Xi,Yj)=longest(LCS(Xi,Yj-1),LCS(Xi-1,Yj)) if Xi!=Yj
} else if(m[i-1][j]>=m[i][j-1]){
m[i][j]=m[i-1][j];
// remember that we kept j constant
b[i][j]=CONST_J;
} else {
m[i][j]=m[i][j-1];
// remember that we kept i constant
b[i][j]=CONST_I;
}
}
}
// construct solution now
j=s2.length;
i=s1.length;
while(j>0&&i>0){
switch(b[i][j]){
case CONST_EQUAL:
// chars in both strings were equal at this point so add them to lcs
lcs.push(s1[i-1]);
i--;j--;
break;
case CONST_I:
j--; // i was constant and j was decremented
break;
case CONST_J:
i--; // j was constant and i was decremented
break;
}
}
return lcs.reverse().join(''); // array to string
}
Problem Statement: Given two strings of characters find longest common subsequence of the two
Solution: We use dynamic programming for solving this problem since this problem exhibits optical substructure property. That is, LCS(longest common subsequence ) of two strings s1 and s2 is also LCS of any prefix of any these strings.
Let Si denote the prefix of S with length i which is less than or equal to Length of S
then
LCS(Ai,Bj) = LCS(Ai-1,Bj-1)+A[i] if A[i]==B[j]
LCS(Ai,Bj) = MAX(LCS(Ai-1,Bj), LCS(Ai,Bj-1) ) if A[i]!=B[j]
so we use a two dimensional array m such that m[i][j] represents the LCS of Ai and Bj
and we can state above laws in terms lengths of LCS as follows
m[i][j] = m[i-1][j-1] +1 if A[i]==B[j]
m[i][j] = max( m[i-1][j], m[i][j-1] ) if A[i]!=B[j]
finally m[A.length][B.length] gives us the maximum length of the longest common subsequence.
In order to get the maximum subsequence we maintain another two dimensional array b, such that b[i][j] in which we remember whether m[i][j] was calculated using m[i-1][j-1]+1 or m[i-1][j] or m[i][j-1].
Array be is then used to generate subsequence by extracting characters from A and B.