string - The most effective string replace alogrithm?

Question

We know that most code editors implement the string search with the Boyer-Moore algorithm.How does it implements the string replace algorithm, Any idea?

Answer 1

我猜现在大多数文本编辑器要么使用单个内存块来保存整个文件，要么使用一组行或更大尺寸的块，每个都指向自己的内存块。（过去使用了更有趣的技术。一种方法是让光标位置左侧或上方的所有文本“压在”固定大小缓冲区的左端，以及右侧或下方的所有文本“压在”右端，中间有一个空闲空间。然后插入或删除字符的常见操作可以在恒定时间内进行！将光标向右移动k个位置需要从左端滑动k个字节右段到左段的右端，即移动光标现在是线性时间操作！）

假设文本以“普通”方式存储（即不是上面描述的左右光标依赖的缓冲区对），没有太多方法可以优化替换操作，特别是如果替换文本比搜索长text——在这种情况下，没有逃避这样一个事实，即行/块/文件的其余部分必须在每次替换时在内存中向前分流。你能做的最好的事情就是避免多次 O(n) 复制操作——即不要删除搜索字符串，然后一次插入一个替换字符串，将行/块/文档的其余部分一次分流一个字符，因为后一步将花费 O(n^2) 时间。相反，将文档文本的其余部分分流到足够远的位置，以便在一个 O(n) 步骤中为替换字符串腾出空间。

如果替换字符串比搜索文本短，您可以使用两个指针from和向前扫描to，始终从一个复制到另一个。随着替换的进行，to将开始落后from。这是安全的，因为它to <= from始终有效，因此您永远不会写下您以后必须阅读的内容。

实际上，如果替换字符串比搜索字符串长，并且搜索字符串的没有后缀也是搜索字符串的前缀，那么您可以安全地从末尾向后扫描一次 O(n) 遍。后缀/前缀要求是必要的，以避免出现以下情况，这些情况会根据扫描方向产生不同的行为：

Search and replace "abcabc" with "xyz" in document text "abcabcabc":
S&R using forward algo gives:  xyzabc
S&R using backward algo gives: abcxyz