// определение минимальной длины ключа и Longest Common Prefix
let len, lcp;
for (let key of keys) {
  // первый элемент
  if (lcp === undefined) {
    len = key.length;
    lcp = key.slice(off);
    continue;
  }
  len = Math.min(len, key.length);
  // пропускаем, если уже "обнулили" LCP или он совпадает для этого элемента
  if (lcp == '' || key.startsWith(lcp, off)) {
    continue;
  }
  // усечение LCP при несовпадении префикса
  for (let i = 0; i < lcp.length; i++) {
    if (lcp.charCodeAt(i) != key.charCodeAt(off + i)) {
      lcp = lcp.slice(0, i);
      break;
    }
  }
}

// перебираем варианты выбора номера тестируемого символа
let grp = new Set();
res.pos = {};
for (let i = off + lcp.length; i < len; i++) {
  // группируем ключи по соответствующим значениям [i]-символа
  let chr = keys.reduce((rv, key) => {
    if (key.length < i) {
      return rv;
    }
    let ch = key.charCodeAt(i);
    rv[ch] = rv[ch] || [];
    rv[ch].push(key);
    return rv;
  }, {});
  // не обрабатываем повторно уже встречавшуюся комбинацию распределений ключей по группам
  let cmb = Object.values(chr)
    .map(seg => seg.join('\t'))
    .sort()
    .join('\n');
  if (grp.has(cmb)) {
    continue;
  }
  else {
    grp.add(cmb);
  }
  res.pos[i] = chr;
}

{
  '$pos' : 2 // проверяем 3-й символ
, '$chr' : Map {
    100 => {         // 'd'
      '$pos' : 6 // проверяем 7-й символ
    , '$chr' : Map {
        79 => [ 'Index Only Scan Backward', 'Index Only Scan' ] // 'O'
      , 83 => [ 'Index Scan Backward', 'Index Scan' ]           // 'S'
      }
    }
  , 115 => 'Insert' // 's'
  }
}

// заполнение карты поиска
const fill = (obj, off, hash) => {
  off = off || 0;
  hash = hash || {};
  let keys = obj.src;
  // проверка наличия такого списка ключей среди уже обработанных
  let H = keys.join('\n');
  hash[off] = hash[off] || {};
  if (hash[off][H]) {
    obj.res = hash[off][H];
    return;
  }
  obj.res = {};
  hash[off][H] = obj.res;
  let res = obj.res;
  // ситуация единственного ключа - возможна только при стартовом вызове
  if (keys.length == 1) {
    res.lst = [...keys];
    res.cmp = res.lst[0].length;
    return;
  }
  // определение минимальной длины ключа и Longest Common Prefix
  let len, lcp;
  for (let key of keys) {
    // первый элемент
    if (lcp == undefined) {
      len = key.length;
      lcp = key.slice(off);
      continue;
    }
    len = Math.min(len, key.length);
    // пропускаем, если уже "обнулили" LCP или он совпадает для этого элемента
    if (lcp == '' || key.startsWith(lcp, off)) {
      continue;
    }
    // усечение LCP при несовпадении префикса
    for (let i = 0; i < lcp.length; i++) {
      if (lcp.charCodeAt(i) != key.charCodeAt(off + i)) {
        lcp = lcp.slice(0, i);
        break;
      }
    }
  }
  // если один из ключей является общим префиксом
  if (off + lcp.length == len) {
    let cmp = 0;
    // для двух ключей оптимальный вариант поиска - список
    if (keys.length == 2) {
      res.lst = [...keys];
    }
    // выносим "за скобки" слишком короткие ключи
    else {
      res.src = keys.filter(key => key.length > off + lcp.length);
      res.lst = keys.filter(key => key.length <= off + lcp.length);
    }
    // поиск по списку проходит, начиная с самого длинного ключа, и стоит дорого
    res.lst.sort((x, y) => y.length - x.length); // s.length DESC
    cmp += res.lst.reduce((rv, key, idx, keys) => rv + (keys.length - idx + 1) * key.length, 0);
    // если есть продолжение - копаем дальше
    if (res.src && res.src.length) {
      fill(res, off + lcp.length + 1, hash);
      cmp += res.res.cmp;
    }
    res.cmp = cmp + 1;
    return;
  }
  // перебираем варианты выбора номера тестируемого символа
  let grp = new Set();
  res.pos = {};
  for (let i = off + lcp.length; i < len; i++) {
    // группируем ключи по соответствующим значениям [i]-символа
    let chr = keys.reduce((rv, key) => {
      if (key.length < i) {
        return rv;
      }
      let ch = key.charCodeAt(i);
      rv[ch] = rv[ch] || [];
      rv[ch].push(key);
      return rv;
    }, {});
    // не обрабатываем повторно уже встречавшуюся комбинацию распределений ключей по группам
    let cmb = Object.values(chr)
      .map(seg => seg.join('\t'))
      .sort()
      .join('\n');
    if (grp.has(cmb)) {
      continue;
    }
    else {
      grp.add(cmb);
    }
    let fl = true;
    let cmp = 0;
    for (let [ch, keys] of Object.entries(chr)) {
      // упаковываем группы из единственного ключа
      if (keys.length == 1) {
        let key = keys[0];
        chr[ch] = key;
        cmp += key.length;
      }
      // для групп из нескольких ключей запускаем рекурсию
      else {
        fl = false;
        chr[ch] = {src : keys};
        fill(chr[ch], i + 1, hash);
        cmp += chr[ch].res.cmp;
      }
    }
    res.pos[i] = {
      chr
    , cmp
    };
    // запоминаем позицию "лучшего" символа
    if (res.cmp === undefined || cmp + 1 < res.cmp) {
      res.cmp = cmp + 1;
      res.bst = i;
    }
    // если за каждым символом остался конкретный ключ, то другие варианты нам не нужны
    if (fl) {
      res.bst = i;
      for (let j = off; j < i; j++) {
        delete res.pos[j];
      }
      break;
    }
  }
};
// сжатие карты поиска в минимальный формат
const comp = obj => {
  // удаляем служебные ключи
  delete obj.src;
  delete obj.cmp;
  if (obj.res) {
    let res = obj.res;
    if (res.pos !== undefined) {
      // сохраняем только оптимальный вариант проверяемого символа
      obj.$pos = res.bst;
      let $chr = res.pos[res.bst].chr;
      Object.entries($chr).forEach(([key, val]) => {
        // упаковываем содержимое ключа
        comp(val);
        // если внутри символа только список - "поднимаем" его на уровень выше
        let keys = Object.keys(val);
        if (keys.length == 1 && keys[0] == '$lst') {
          $chr[key] = val.$lst;
        }
      });
      // преобразуем объект с ключами-строками в Map с ключами-числами
      obj.$chr = new Map(Object.entries($chr).map(([key, val]) => [Number(key), val]));
    }
    // при наличии списка "поднимаем" вложенные результаты на уровень выше
    if (res.lst !== undefined) {
      obj.$lst = res.lst;
      delete res.lst;
      if (res.res !== undefined) {
        comp(res);
        Object.assign(obj, res);
      }
    }
    delete obj.res;
  }
};
// поиск по карте - циклы вместо рекурсии и замыканий
const find = (str, off, map) => {
  let curr = map;
  do {
    // по символу в позиции
    let $pos = curr.$pos;
    if ($pos !== undefined) {
      let next = curr.$chr.get(str.charCodeAt(off + $pos));
      if (typeof next === 'string') {   // значение ключа
        if (str.startsWith(next, off)) {
          return next;
        }
      }
      else if (next instanceof Array) { // список ключей на проверку
        for (let key of next) {
          if (str.startsWith(key, off)) {
            return key;
          }
        }
      }
      else if (next !== undefined) {    // вложенный map, если есть
        curr = next;
        continue;
      }
    }
    // ищем по дополнительному списку, если он есть
    if (curr.$lst) {
      for (let key of curr.$lst) {
        if (str.startsWith(key, off)) {
          return key;
        }
      }
    }
    return;
  }
  while (true);
};
function ImmutableTrie(keys) {
  this.map = {src : keys.sort((x, y) => x < y ? -1 : +1)};
  fill(this.map);
  comp(this.map);
}
const p = ImmutableTrie.prototype;
p.get = function(line, off) {
  return find(line, off || 0, this.map);
};
p.has = function(line, off) {
  return this.get(line, off) !== undefined;
};
module.exports = ImmutableTrie;

const nodeIT = new ImmutableTrie(...);
nodeIT.get('  ->  Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'

Index Scan using pg_class_relname_nsp_index on pg_class  (cost=0.29..2.54 rows=1 width=265) (actual time=0.014..0.014 rows=0 loops=1)
  Index Cond: (relname = 'мама\nмыла\nраму'::name)
  Buffers: shared hit=2