Я создал 2 файла для самопроверки, вписал туда закодирванные строки.
Идея была такова: для начала найти longest common sequence , затем выделить элементы, которые не вошли в эту последовательность. LCS мы получаем с помощью алгоритма Ханта-Шуманского. Затем мы получим словарь элементов, которые пропали из оригинала, и словарь элементов, которые появились в новом файле. Когда мы полуили разницу, мы можем по этим полученным словарям легко восстановить новый файл. Сначала испорльзуем словарь удаленных элементов, удаляем элементы из оригинала, затем втсавляем элементы на места , которые отражены в словаре новых элементов.
В коде orig относится к оригиналу, а upd относится к новому файлу.