Создайте двоичное дерево, представляющее документ до и после применения всех изменений. Каждый узел представляет собой либо оригинальный текст, либо вставленный / удаленный текст; последний тип узла включает в себя как количество исходного текста для удаления (возможно, 0), так и строку текста для вставки (возможно, пустую).
Первоначально дерево имеет только один узел: «0 до конца: исходный текст». Примените все изменения к нему, объединяя изменения, когда вы идете, где это возможно. Затем пройдитесь по дереву от начала до конца, испуская последний набор правок. Это гарантированно даст оптимальный результат.
Применение вставки: найдите соответствующую точку в дереве. Если он находится в середине или рядом с вставленным текстом, просто измените строку текста для вставки этого узла. В противном случае добавьте узел.
Применение удаления: найдите начальную и конечную точки в дереве - в отличие от вставки, удаление может охватывать весь диапазон существующих узлов. Измените начальный и конечный узлы соответственно и уничтожьте все промежуточные узлы. После того, как вы закончите, проверьте, есть ли у вас смежные узлы «вставленный / удаленный текст». Если это так, присоединяйтесь к ним.
Единственный хитрый момент - убедиться, что вы можете найти точки в дереве, не обновляя все дерево каждый раз, когда вы вносите изменения. Это делается путем кэширования на каждом узле общего объема текста, представленного этим поддеревом. Затем, когда вы вносите изменения, вам нужно только обновить эти кэшированные значения на узлах, непосредственно выше узлов, которые вы изменили.
Это выглядит строго O (n log n) для всех входных данных, если вы хотите реализовать сбалансированное дерево и использовать веревки для вставленного текста. Если вы отказываетесь от идеи всего дерева и используете векторы и строки, это O (n 2 ), но на практике может хорошо работать.
Рабочий пример. Вот как этот алгоритм будет применяться к вашему примеру, шаг за шагом. Вместо того, чтобы делать сложные ascii art, я поверну дерево на бок, покажу узлы по порядку и покажу структуру дерева по отступам. Надеюсь, это понятно.
Исходное состояние:
*: orig
Я сказал выше, что мы будем кэшировать количество текста в каждом поддереве. Здесь я просто поставил * для количества байтов, потому что этот узел содержит весь документ, и мы не знаем, как долго это будет. Вы можете использовать любое достаточно большое число, например, 0x4000000000000000L.
После вставки «ab» в положение 2:
2: orig, 2 bytes
*: insert "ab", delete nothing
*: orig, all the rest
После вставки «cde» в положение 1:
1: orig, 1 byte
5: insert "cde", delete nothing
1: orig, 1 byte
*: insert "ab", delete nothing
*: orig, all the rest
Следующим шагом является удаление символа в позиции 4. Сделайте паузу здесь, чтобы увидеть, как мы находим позицию 4 в дереве.
Начать с корня. Посмотрите на первый дочерний узел: это поддерево содержит 5 символов. Таким образом, позиция 4 должна быть там. Перейти к этому узлу. Посмотрите на его первый дочерний узел. На этот раз он содержит только 1 символ. Не там. Эта правка содержит 3 символа, поэтому здесь ее тоже нет; это сразу после. Перейти ко второму дочернему узлу. (Этот алгоритм содержит около 12 строк кода.)
После удаления 1 символа в позиции 4 вы получите это ...
4: orig, 1 byte
3: insert "cde", delete nothing
*: insert "ab", delete nothing
*: orig, all the rest
... и затем, заметив два соседних узла вставки, вы объединяете их. (Обратите внимание, что с учетом двух смежных узлов один всегда находится где-то выше другого в древовидной иерархии. Объедините данные в этот более высокий узел; затем удалите более низкий и обновите размеры кэшированного поддерева между ними.)
1: orig, 1 byte
*: insert "cdeab", delete nothing
*: orig, all the rest