keyed list diff algorithm created by charlesouyang - https://repl.it/@charlesouyang/keyed-list-diff-algorithm

index.js

// actions constants
const REMOVE = 'REMOVE';
const INSERT = 'INSERT';
const MOVE = 'MOVE';

/**
 * calculate LIS (positive numbers only)
 * @param arr array of number
 */
const calcLis = function (arr) {
  const M = [-1]; // marks
  const P = []; // previous path
  const S = []; // result sequence
  let i, left, mid, right, len;
  for (i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      continue;
    }
    left = 1;
    right = arr.length;
    while (left < right) {
      mid = Math.floor((left + right) / 2);
      if (arr[M[mid]] <= arr[i]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    M[left] = i;
    P[i] = M[left - 1];
  }
  len = M.length - 1;
  i = M[len];
  while (i !== -1) {
    S[len-- - 1] = arr[i];
    i = P[i];
  }
  return S;
};

/**
 * trim same elements for two arrays, return deviation counts of beginning
 * and ending
 * @param list1 new sequence
 * @param list2 old sequence
 */
const trimTwoLists = function (list1, list2) {
  let sd = 0;
  let ed = 0;
  let idx1 = 0, idx2 = 0;
  const { length: len1 } = list1;
  const { length: len2 } = list2;
  while (sd < len1 && sd < len2 && list1[idx1].key === list2[idx1].key) {
    sd++;
    idx1 = sd;
    idx2 = sd;
  }
  idx1 = len1 - ed - 1;
  idx2 = len2 - ed - 1;
  while (sd + ed < len1 && sd + ed < len2 && list1[idx1].key === list2[idx2].key) {
    ed++;
    idx1 = len1 - ed - 1;
    idx2 = len2 - ed - 1;
  }
  return [sd, ed];
};

/**
 * diff two arrays of number, Takes O(nlogn) time in expectation
 * @param list1 array of characters
 * @param list2 array of characters
 */
const diff = function (list1, list2) {
  const { length: len1 } = list1;
  const { length: len2 } = list2;
  const [sd, ed] = trimTwoLists(list1, list2);
  const PTailIns = []; // tail insertions
  const PMovs = []; // move patches
  const IM = new Map(); // index map
  const IT = new Array(len2 - sd - ed).fill(-1); // key table
  let shouldMoved = false; // no need to move if LIS.length == IT.length(positive numbers only)
  let i, j, k, end, last, patch; // other temp variables
  for (i = sd, end = len2 - ed; i < end; i++) {
    IM.set(list2[i].key, i);
  }
  last = -1;
  for (i = sd, end = len1 - ed; i < end; i++) {
    j = IM.get(list1[i].key);
    if (j !== undefined) {
      IT[j - sd] = i;
      if (j < last) {
        shouldMoved = true;
      } else {
        last = j;
      }
    } else {
      list1[i].patch.type = REMOVE;
    }
  }
  const LIS = calcLis(IT);
  last = IT.length;
  for (i = len2 - ed - 1, j = LIS.length - 1, end = sd - 1; i > end; i--) {
    k = i - sd;
    if (IT[k] === -1) {
      if (last !== IT.length) {
        ({ patch } = list1[IT[last]]);
        patch.type = INSERT;
        (patch.payload = patch.payload || []).push(list2[i]);
      } else {
        PTailIns.push(list2[i]);
      }
    } else if (shouldMoved) {
      if (j < 0 || LIS[j] !== IT[k]) {
        PMovs.push({ type: MOVE, payload: [list2[i], IT[last] === undefined ? len1 : IT[last]] });
      } else {
        j--;
      }
    }
    last = IT[k] === -1 ? last : k;
  }
  return [PMovs, PTailIns, list1];
};

/**
 * normalize sequence
 * @param strSeq string sequence
 */
const prepareData = function (strSeq) {
  const list = strSeq.split('').map(s => ({
    key: s,
    patch: {},
    next: null
  }));
  let i, len;
  for (i = 0, len = list.length - 1; i < len; i++) {
    list[i].next = list[i + 1];
  }
  return list;
};

/**
 * print sequence
 * @param seq sequence
 */
const printSeq = function (seq) {
  console.log('SEQ:\t' + seq.reduce((acc, item) => {
    acc.push(item.key);
    return acc;
  }, []));
};

/**
 * reconcile diffs, here we just print it
 * @param P position move patches
 * @param la patched origin list
 */
const reconcile = function (P) {
  const [movs, PTailIns, list] = P;
  let i, j, len, key, type, payload;
  for (i = 0, len = movs.length; i < len; i++) {
    ({ payload } = movs[i]);
    console.log(`move\t${payload[0].key}   before ${payload[1]}(index)`);
  }
  for (i = PTailIns.length - 1, len = -1; i > len; i--) {
    console.log(`insert\t${PTailIns[i].key}   before ${list.length + PTailIns.length - i - 1}(index)`);
  }
  for (i = list.length - 1, len = -1; i > len; i--) {
    ({ key, patch: { type, payload } } = list[i]);
    if (type === REMOVE) {
      console.log(`remove\t${key} ${i}`);
    } else if (type === INSERT) {
      for (j = payload.length - 1; j > -1; j--) {
        console.log(`insert\t${payload[j].key}   before ${list[i].key}(item)`);
      }
    }
  }
};

// test, NOTE: character shall be unique in each sequence
const la = prepareData('hagb');
const lb = prepareData('adbgc');

printSeq(la);
printSeq(lb);

const P = diff(la, lb);
reconcile(P);