longest common sub series

LCS.js

/**
 *
 * @param {ArrayLike} sa - series a
 * @param {ArrayLike} sb - series b
 * @param {boolean} [isContinuous=false] - is sub series continuous
 * @returns {Array<Array<any>>} - all longest common series
 */
function longestCommonSeries(sa, sb, isContinuous = false) {
    if (sa.length === 0 || sb.length === 0) {
        return [];
    }

    let map = new Array(sa.length + 1);

    for (let i = 0; i <= sa.length; i++) {
        map[i] = [];
        map[i][0] = 0;
    }

    for (let j = 0; j <= sb.length; j++) {
        map[0][j] = 0;
    }

    for (let i = 1; i <= sa.length; i++) {
        for (let j = 1; j <= sb.length; j++) {
            if (sa[i - 1] === sb[j - 1]) {
                map[i][j] = map[i - 1][j - 1] + 1;
            } else {
                if (map[i - 1][j] >= map[i][j - 1]) {
                    map[i][j] = map[i - 1][j];
                } else {
                    map[i][j] = isContinuous ? 0 : map[i][j - 1];
                }
            }
        }
    }

    if (isContinuous) {
        return findContinuousLCS(sa, sb, map);
    }

    return findLCS(sa, sb, map);
}

function findContinuousLCS(sa, sb, map) {
    let biggest = -1;
    let indexes = [];
    let i = sa.length;
    for(let j = 1; j <= sb.length; j++) {
        if (biggest < map[i][j]) {
            biggest = map[i][j];
            indexes = [j];
        } else if (biggest === map[i][j]) {
            indexes.push(j);
        }
    }

    return indexes.reduce((series, index) => {
        series.push(sb.slice(index - biggest, index))
        return series;
    }, [])
}

function findLCS(sa, sb, map) {
    let lcs = [];
    const getLCS = (i, j, s = []) => {
        while (i > 0 && j > 0) {
            if (sa[i - 1] === sb[j - 1]) {
                s.push(sa[i - 1])
                i--;
                j--;
            } else if (map[i - 1][j] > map[i][j - 1]) {
                i--;
            } else if (map[i - 1][j] < map[i][j - 1]) {
                j--;
            } else {
                getLCS(i - 1, j, s);
                getLCS(i, j - 1, s);
            }
        }
        lcs.push(s.reverse());
    }
    getLCS(sa.length, sb.length);
    return lcs;
}