javascript - 使用动态编程而不是递归来找到最大的公共后缀（javascript）

Question

我找到了一个递归解决方案来找到两个字符串的最大公共后缀。如何将其转换为动态编程解决方案。我很难概念化一个自下而上的解决方案，因为后缀最容易从两个字符串的末端进行比较。我有一个尝试过的解决方案，但对我来说似乎是自上而下。

试图

var LCSuffDyn = function(X,Y) {
    longest_suffix = [''];
    var largest_string, smallest_string;
    if (X.length > Y.length) {
        largest_string = X;
        smallest_string = Y;
    } else {
        largest_string = Y;
        smallest_string = X;
    }

    for (var k=1; k<smallest_string.length; k++) {
        if (X[X.length-k] === Y[Y.length-k]) {
            longest_suffix[k] = X[X.length-k]+longest_suffix[k-1];
        }
        else break;
    }

    return longest_suffix[longest_suffix.length-1];
};
console.log(LCSuffDyn('cbbbbbbbbbbajlbbbbbbbaba', 'cajkbbbbbbbbbjklbaba'));

递归的

var LCSuffRec = function(X,Y) {
    return rec(X,Y, X.length, Y.length);
    function rec(X, Y, m, n) {
        if (X[m-1] === Y[n-1]) return rec(X, Y, m-1, n-1) + X[m-1];
        else return '';
    }
};

Answer 1

像这样试试

    function LCSuffDyn( X, Y ) {
    var result = "";
    var indexX = X.length - 1;
    var indexY = Y.length - 1;
    var endIt = false;
    while( indexX >= 0 && indexY >= 0 && !endIt ) {
        if( X.substr( indexX, 1 ) == Y.substr( indexY, 1 ) ) {
            result = X.substr( indexX, 1 ) + result;
        } else {
            endIt = true;
        }
        indexX --;
        indexY --;
    }
    return result;
}

在这里演示