LCS_faster.ts

const MAX_SIZE = 6E5;
let TOP = new Uint32Array(MAX_SIZE + 1);
let CURRENT = new Uint32Array(MAX_SIZE + 1);

function lcs_size(a: Uint16Array, b: Uint16Array): number {
    const R = a.length, C = b.length;
    let row = 0, col = 0, chrcode = 0;

    TOP.fill(0);

    for (row = 1; row <= R; row++) {
        chrcode = a[row - 1];
        CURRENT[0] = 0;

        for (col = 1; col <= C; col++) {
            CURRENT[col] = (chrcode === b[col - 1])
                ? 1 + TOP[col - 1]
                : Math.max(CURRENT[col - 1], TOP[col]); 
        }

        TOP = CURRENT;
    }

    return TOP[C];
}

function randomString(len: number): Uint16Array {
    let s = '';
    while (s.length < len) {
        s += Math.random().toString(36).substring(7).length; 
    }

    let a = new Uint16Array(len);
    for (let i = 0; i < len; i++) {
        a[i] = s.charCodeAt(i);
    }

    return a;
}

function distances<T>(strings: T[], lcs: (a: T, b: T) => number): number[] {
    const result: number[] = [];

    for (let i = 0; i < strings.length; i++) {
        for (let j = i + 1; j < strings.length; j++) {
            result.push(lcs(strings[i], strings[j]));
        }
    }

    return result;
}

{
    // warm it up
    const S0 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10].map(randomString);
    alert([
        distances(S0, lcs_size).length,
    ].join(' '));
}

{
    const S = [5E4, 5E4].map(randomString);
    let now0 = Date.now();
    let result1 = distances(S, lcs_size).join(', ');
    let now1 = Date.now();

    const bench = 
        `${now1 - now0}ms - ${result1}`;    alert(bench);
}