Skip to content

Instantly share code, notes, and snippets.

@abarth500
Forked from greduan/lcs.js
Last active January 17, 2018 08:32
Show Gist options
  • Save abarth500/5658fb19e0f5d8e8d63b31f5da825767 to your computer and use it in GitHub Desktop.
Save abarth500/5658fb19e0f5d8e8d63b31f5da825767 to your computer and use it in GitHub Desktop.
LCS algorithm in JS. Prettified version of what can be found here: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence#JavaScript
// prettified version of what can be found here:
// https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence#JavaScript
function LCS(a, b) {
var m = a.length,
n = b.length,
C = [],
i,
j;
for (i = 0; i <= m; i++) C.push([0]);
for (j = 0; j < n; j++) C[0].push(0);
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
C[i+1][j+1] = a[i] === b[j]
? C[i][j]+1
: Math.max(C[i+1][j], C[i][j+1]);
}
}
C.forEach(
function(c){
console.log(c.map(
function(d){
return ('0'+d).slice(-2);
}
));
}
);
return (function bt(i, j) {
if (i * j === 0) {
return '';
}
if (a[i-1] === b[j-1]) {
let rtn =bt(i-1, j-1) + a[i-1];
console.log(i,j,rtn);
return rtn;
}
let rtn = (C[i][j-1] > C[i-1][j])
? bt(i, j-1)
: bt(i-1, j);
console.log(i,j,rtn);
return rtn;
}(m, n));
}
console.log(LCS('静岡大学情報学部', '岡山大学工学部'));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment