Сделайте двоичное дерево, представляющее документ до и после применения всех изменений.Каждый узел представляет либо исходный текст, либо вставленный/удаленный текст; последний тип узла включает как количество исходного текста для удаления (возможно, 0), так и строку текста для вставки (возможно, пустую).
Первоначально дерево имеет только один узел, «0 до конца: исходный текст». Примените все изменения к нему, объединяя изменения по мере возможности. Затем пройдите дерево от начала до конца, испустив окончательный набор изменений. Это гарантирует получение оптимального результата.
Применение вставки: найдите соответствующую точку в дереве. Если он находится в середине или рядом с вставленным текстом, просто измените строку текста для вставки этого узла. В противном случае добавьте узел.
Применение удаления: найдите начальную и конечную точки в дереве - в отличие от вставки, удаление может охватывать целый ряд существующих узлов. Измените начальный и конечный узлы соответственно и убейте все узлы между ними. После того, как вы закончите, проверьте, есть ли у вас соседние узлы «вставленный/удаленный текст». Если да, присоединитесь к ним.
Единственный сложный бит - убедиться, что вы можете найти точки в дереве, не обновляя все дерево каждый раз, когда вы вносите изменения. Это делается путем кэширования на каждом узле общей суммы текста, представленного этим поддеревом. Затем, когда вы вносите изменения, вам нужно только обновить эти кешированные значения на узлах непосредственно выше узлов, которые вы изменили.
Это выглядит строго O (n log n) для всех входных данных, если вы хотите реализовать сбалансированное дерево и использовать веревки для вставленного текста. Если вы выбрасываете идею всего дерева и используете векторы и строки, это O (n), но на практике может работать нормально.
Образец примера. Вот как этот алгоритм будет применяться к вашему примеру, шаг за шагом. Вместо того, чтобы делать сложное искусство ascii, я превращу дерево на бок, покажу узлы в порядке и покажу древовидную структуру по отступу. Надеюсь, это ясно.
Исходное состояние:
*: 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
Это очень продуманный пример. В нем показаны многие аспекты, которые нужно использовать для уменьшения количества операций. – Svante