公共最长子序列

从末尾向前算

var naiveLCS = function(str1,str2){
    var result = "";
        //相等先退出
    if(str1.split('').length == 0 || str2.split('').length == 0){
        return false;
    }

    if(str1.substr(-1) == str2.substr(-1)){
        result = naiveLCS(str1.slice(0,-1),str2.slice(0,-1))
        if(result)
            result = result + str1.slice(-1);
        else
            result = str1.slice(-1);
        return result;
    }else{
        var tempR1 = naiveLCS(str1.slice(0,-1),str2);
        var tempR2 = naiveLCS(str1,str2.slice(0,-1));
        if(tempR1 && tempR2){
            return tempR1.split('').length > tempR2.split('').length ? tempR1 : tempR2;
        }else{
            return tempR1 ? tempR1 : tempR2;
        }
    }
}

var a = "12de111q";
var b = "w12e444vq";
console.log(naiveLCS(a,b));