Skip to content

Instantly share code, notes, and snippets.

@nopeless
Created December 9, 2021 15:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nopeless/c1fc9f0e4c9d986e9dd91f38a9570a10 to your computer and use it in GitHub Desktop.
Save nopeless/c1fc9f0e4c9d986e9dd91f38a9570a10 to your computer and use it in GitHub Desktop.
I make 3D lcs in javascript
var crypto = require(`crypto`);
// var a = crypto.randomBytes(20).toString(`hex`);
// var b = crypto.randomBytes(20).toString(`hex`);
// var c = crypto.randomBytes(20).toString(`hex`);
var a = `acc3be0ffe08a5a37546ff6f31c8eab2ce11bd7e`;
var b = `0ded06494ff6017e86257f15f12db11e09ec2664`;
var c = `630fea9f3c2d173718a53d5488f3b53b22e35f88`;
const abc = Array.from({length: a.length + 1}, () =>
Array.from({length: b.length + 1}, () =>
Array(c.length + 1).fill(0),
),
);
for (let ai = 0; ai < a.length; ai++) {
for (let bi = 0; bi < b.length; bi++) {
for (let ci = 0; ci < c.length; ci++) {
if (a[ai] == b[bi] && b[bi] == c[ci]) {
abc[ai + 1][bi + 1][ci + 1] = abc[ai][bi][ci] + 1;
} else {
abc[ai + 1][bi + 1][ci + 1] = Math.max(
abc[ai + 1][bi][ci],
abc[ai][bi + 1][ci],
abc[ai][bi][ci + 1],
abc[ai + 1][bi + 1][ci],
abc[ai][bi + 1][ci + 1],
abc[ai + 1][bi][ci + 1],
);
}
}
}
}
let finalStr = ``;
let l = abc[a.length][b.length][c.length];
// console.log(abc);
let target = l - 1;
let temp = 0;
let ai = a.length;
let bi = b.length;
let ci = c.length;
for (let i = 0; i < l; i++) {
/* eslint-disable no-empty */
const curr = abc[ai][bi][ci];
for (;abc[ai - 1][bi][ci] === curr; ai--) {}
for (;abc[ai][bi - 1][ci] === curr; bi--) {}
for (;abc[ai][bi][ci - 1] === curr; ci--) {}
if (abc[ai - 1][bi - 1][ci - 1] === target) {
target--;
finalStr += a[ai - 1];
ai--;
bi--;
ci--;
}
}
console.log(a);
console.log(b);
console.log(c);
console.log(`Longest (${l}) = `, Array.from(finalStr).reverse().join(``));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment