string - 最有效的字符串替换算法？

Question

我们知道大多数代码编辑器都是通过Boyer-Moore算法实现字符串搜索的。它是如何实现字符串替换算法的，知道吗？

Answer 1

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

假设文本以“普通”方式存储(即不是上面描述的左右游标依赖缓冲区对)，没有太多方法可以优化替换操作，尤其是在替换文本较长的情况下比搜索文本——在这种情况下，不可避免的事实是，每次替换时，行/ block /文件的其余部分必须在内存中向前分流。您可以做的最好的事情是避免多次 O(n) 复制操作，即不要删除搜索字符串，然后一次插入一个字符的替换字符串，分流行/ block /文档的其余部分一次转发一个字符，因为后一步将花费 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