Как применить последовательность операций вставки / удаления символов к строке?

Question

У меня есть такой текст:

Меня зовут Боб, и я живу в Америке.

У меня есть некоторые ссылки на символы этой строки, дляпример:

from 3 to 7 chars, deleted
at 3 char, added "surname"
from 20 to 25, deleted
at 25 char ....

но эти операторы не упорядочены (и я не могу их упорядочить).

Итак, вот вопрос: как я могу изменить текст, не теряяссылка на персонажей?Например, если я применяю первое предложение, мой текст становится:

Мой Боб, и я живу в Америке.

, и мое третье предложение не работает правильнобольше, потому что я потерял ссылку на оригинальный 20-й символ.

Имейте в виду, что текст довольно длинный, поэтому я не могу использовать индексы ...

Answer 1

Прежде всего, если это утверждение верно, ситуация безнадежна:

но эти утверждения не упорядочены (и я не могу их упорядочить).

Неупорядоченный список операторов исправления может привести к конфликту.Невозможно решить, какой правильный ответ будет сделан автоматически.Например, рассмотрим следующую ситуацию:

         0         1         2
 index:  012345678901234567890
 text:  "apple banana coconuts"
    - delete 5 characters from index 10
    - add "xyz" at index 10
    - delete 10 characters from index 5

В результате вы получите различные результаты в зависимости от того, в каком порядке вы выполняете эти операторы .

• Например, если вы примените (1), затем (2), затем (3), вы получите «apple banaconuts» -> «apple banaxyzconuts» -> «apple uts».

• Но если вы примените (3), затем (2), а затем (1), вы получите «apple onuts» -> «apple onutsxyz» -> [error - thereнедостаточно символов для удаления!] .

Либо вам требуется повторяющееся согласованное упорядочение утверждений, либо вы не можете продолжить работу.Хуже того, оказывается, что обнаружение того, какие упорядочения являются действительными (например, устранение всех упорядочений, где встречается невозможное утверждение, например «удалить 10 символов из индекса 20», когда нет индекса 20), является неразрешимая проблема информатики .

Если окажется, что исправления могут быть применены в определенном порядке (или, по крайней мере, в повторяющемся, согласованном, детерминированном порядке), ситуация улучшается, но все еще неприятна.Поскольку индексы в любом «патче» могут быть признаны недействительными по сравнению с любым предыдущим, не представляется возможным напрямую применить каждое утверждение.Вместо этого вам придется реализовать небольшой псевдо-diff.Вот как я это сделаю:

• Просматривать список операторов-патчей.Составьте список операций .Операция - это объект с командой и некоторыми необязательными аргументами и index для применения этой команды.Например, ваши операции могут выглядеть следующим образом:

  DeleteOperation(index 3, length 4)
  AddOperation(index 3, text "surname")
  DeleteOperation(index 20, length 5)

• По мере выполнения операций сохраняйте ссылку на исходную строку и сохраняйте «грязный»указатель".Это последний непрерывный индекс в строке, в котором не было выполнено никаких операций.Любая выполняемая вами операция, индекс которой превышает «грязный» указатель, должна быть предварительно обработана.

• Если вы встретите чистую операцию, индекс которой меньше или равен «грязному» указателю, выможет применить его без дальнейшей работы.Грязный указатель теперь перемещается к индексу этой операции.

• Если вы столкнулись с грязной операцией, индекс которой больше, чем грязный указатель, вам придется выполнить некоторую работу, прежде чем вы сможетеприменить это.Определите реальный индекс того, где операция должна применяться, просмотрев предыдущие операции, затем сделайте соответствующее смещение и примените его.

• Выполняйте каждую операцию по очереди, пока не останется больше операцийвыполнить.

Результатом будет ваша преобразованная строка.

Answer 2

Что именно вы пытаетесь сделать здесь?

Если вы пытаетесь применить эти «ссылки» к вашему тексту,

Меня зовут Боб, и я живу в Америке.

Сохранить эти данные без изменений. Скопируйте это в другую строку и применяйте вашу «ссылку» там каждый раз, когда вам нужно изменить ее.

Answer 3

Каждый раз, когда вы выполняете оператор, просмотрите весь список и соответствующим образом измените индексы.

Answer 4

Звучит так, как будто вы делаете Операционные преобразования

В этой статье мы обсудим их в теории и на практике (и довольно подробно)

Понимание и применение операционной трансформации

Если они не в каком-либо порядке, как вы можете их применить?Как узнать, следует ли применять одну операцию до или после другой операции?Ни одна из операций не является аддитивной?(т.е.: все ли операции применимы только к исходной строке?)

Answer 5

Вам просто нужно будет отследить, что вы делаете со строкой, и добавить или вычесть из будущих индексов элементов в своем списке команд.