Longest Common Subsequence

沒想到有一天實際上會用到這個問題
用wiki上面的演算法實作javascript

var LCSTable = function(X, Y){
//Longest Common Subsequence
X.splice(0,0,0);
Y.splice(0,0,0);
var C = new Array(X.length);
for(var i=0; i<X.length; i++){
C[i]= new Array(Y.length)
for(var j=0; j<Y.length; j++){
if( i*j === 0){
C[i][j] = 0
}else if(X[i] === Y[j]){
//element in common
C[i][j] = C[i-1][j-1] +1;
}else{
C[i][j] = Math.max(C[i][j-1], C[i-1][j]);
}
}
console.log(C[i])
}
return C;
}
var LCSTraceback = function(C, X, Y, i, j){
console.log(i +','+ j)
if(i === 0 || j === 0){
return []
}else if(X[i] === Y[j]){
var LCS = LCSTraceback(C, X, Y, i-1, j-1)
LCS.push(X[i])
return LCS
}else if(C[i][j-1] >= C[i-1][j]){
return LCSTraceback(C, X, Y, i, j-1)
}else{
return LCSTraceback(C, X, Y, i-1, j)
}
}

X=[2,3,4,5,8,9,8,7]
Y=[4,5,6,9,8,5,7]
C = LCSTable(X,Y)
LCS = LCSTraceback(C, X, Y, X.length-1, Y.length-1)
console.log(LCS)
[4, 5, 9, 8, 7]