Instantly share code, notes, and snippets.

@qti3e /lcs.ts
Created Mar 24, 2018

Embed
What would you like to do?
Longest common substring
function Int2DArray(a: number, b: number) {
const data = new Int32Array(a * b);
return {
set(i: number, j: number, v: number) {
const index = j * a + i;
data[index] = v;
},
get(i: number, j: number) {
const index = j * a + i;
return data[index];
}
}
}
export function LCSubstr(s: string,t: string) {
const r = s.length;
const n = t.length;
const L = Int2DArray(r, n);
// size of longest common substring
let z = 0;
// last index of matched string
let ret = new Int16Array(Math.ceil(Math.min(r, n) / 2));
let cur = 0;
for (let i = 0; i < r; ++i) {
for (let j = 0; j < n; ++j) {
if (s[i] === t[j]) {
if (i === 1 || j === 1) {
L.set(i, j, 1);
} else {
L.set(i, j, L.get(i - 1, j - 1) + 1);
}
if (L.get(i, j) > z){
z = L.get(i, j);
cur = 0;
ret[cur] = i;
} else if (L.get(i, j) === z){
cur += 1;
ret[cur] = i;
}
} else {
L.set(i, j, 0);
}
}
}
cur += 1;
const substrings = [];
for (let i = 0; i < cur; ++i) {
substrings.push(s.substr(ret[i] - z, z + 1));
}
return substrings;
}
console.log(LCSubstr("ABABC", "BABCA"));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment