java - 如何对字符串应用一系列插入/删除字符操作？

Question

我有这样一段文字:

My name is Bob and I live in America.

我对这个字符串的字符有一些引用，例如:

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

但这些语句没有排序(我无法排序)。

那么，问题来了:如何在不丢失字符引用的情况下修改文本？ 例如，如果我应用第一句话，我的文本就变成了:

My is Bob and I live in America.

我的第三句话不再正确工作，因为我丢失了对原始第 20 个字符的引用。

请记住，文本很长，所以我不能使用任何索引...

Answer 1

首先，如果这个说法是真的，情况就没有希望了:

but these statements aren't ordered (and I can't order them).

补丁语句的无序列表可能会导致冲突。不可能以自动方式决定正确答案是什么。例如，考虑以下情况:

         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没有足够的字符删除!]。

要么您需要一个可重复的、商定的语句顺序，要么您无法继续进行。更糟糕的是，事实证明，发现哪些排序是有效的(例如，消除出现不可能语句的所有排序，如“从索引 20 中删除 10 个字符”，当没有索引 20 时)是一个 undecidable computer science problem .

---

如果事实证明可以按特定顺序(或至少按可重复的、商定的、确定性的顺序)应用补丁，情况会有所改善，但仍然令人讨厌。因为任何“补丁”中的索引都可能被任何先前的索引无效，所以不可能直接应用每个语句。相反，您必须实现一个小的伪 diff。以下是我的做法:

• 浏览补丁声明列表。构建一个操作列表。一个操作是一个对象，带有一个命令和一些可选的参数，以及一个应用该命令的索引。例如，您的操作可能如下所示:

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

• 在执行操作时，保留对原始字符串的引用并存储一个“脏指针”。这是字符串中未对其执行任何操作的最新连续索引。您执行的任何索引超过脏指针的操作都必须首先进行预处理。

• 如果您遇到一个干净的操作，其索引小于或等于脏指针，您可以应用它而无需进一步的工作。脏指针现在移动到该操作的索引。

• 如果您遇到脏操作，其索引大于脏指针，您必须先做一些工作才能应用它。通过查看之前的操作确定应该在何处应用操作的真实索引，然后进行适当的偏移并应用它。

• 依次执行每个操作，直到没有更多的操作要执行。

结果是您转换后的字符串。