Find Longest Common String

findLongestCommonString.ts

const S = "sustainable";
const K = "disabling";

interface Tree {
  [char: string]: Tree;
}

function buildTree(str: string): Tree {
  const tree: Tree = {};
  const prevs = [tree];

  for (const c of str) {
    tree[c] = tree[c] || {};

    prevs.forEach((prev, i) => {
      console.log("tree");

      prev[c] = prev[c] || {};
      prevs[i] = prev[c];
    });

    prevs.push(tree[c]);
  }

  return tree;
}

function findLongestCommonString(s1: string, s2: string): string {
  const shortest = s1.length >= s2.length ? s2 : s1;
  const longest = s1.length >= s2.length ? s1 : s2;
  const tree = buildTree(shortest);

  let result = "";

  for (let i = 0, c = longest.length; i < c; ++i) {
    let foundLen = 0;
    let node = tree;

    for (let i2 = i, c = longest.length; i2 < c; ++i2) {
      const c = longest[i2];

      console.log("search");

      if (!node[c]) {
        break;
      } else {
        node = node[c];
        foundLen++;
      }
    }

    if (foundLen > result.length) {
      result = longest.substring(i, i + foundLen);
    }
  }

  return result;
}

console.clear();
console.log(findLongestCommonString(S, K));