Skip to content

Instantly share code, notes, and snippets.

@qti3e 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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.