JavaScript 获取两个字符串最长公共子串 (Longest Common Subsequence)

获取两个字符串 a 和 b 的最长公共子串，时间复杂度 O(mn)，空间复杂度 O(n)，其中 a 的字符串长度为 m，b 的字符串长度为 n。

function lcs(a, b) {
    var ai, al = a.length,
        bi, bl = b.length - 1, maxBi,
        max = 0, val,
        row = [],
        ret = [];

    for (ai = 0; ai < al; ai++) {
        for (bi = bl; bi > -1; bi--) {
            val = a[ai] == b[bi] ? 1 : 0;
            if (val) {
                if (row[bi - 1]) {
                    val += row[bi - 1];
                }
                if (val > max) {
                    max = val;
                    maxBi = bi;
                }
            }
            row[bi] = val;
        }
    }

    for (; max > 0; max--, maxBi--) {
        ret.unshift(b[maxBi]);
    }

    return ret.join('');
}