string - 支持追加、前置和搜索操作的字符串数据结构

Question

我需要构建一个文本编辑器作为我的迷你项目，并且我需要设计一个支持以下操作的数据结构或算法：

• Append：在字符串末尾追加一个字符。
• Prepend：在字符串的开头添加一个字符。
• Search：给定一个搜索字符串 s，找到该字符串的所有出现。

每个操作在 O(log n) 时间或更短的时间内完成。搜索和替换操作将是可观的，但不是必需的。字符串的最大长度是恒定的。任何想法如何实现这一目标？

谢谢！

Answer 1

这种应用程序的常见数据结构是Rope，其中 Append 和 Prepend 是 O(1)，尽管这在一定程度上取决于树是否平衡。然而，正如Толя所指出的，搜索将是线性的。

当然有一些数据结构可以使搜索更快，例如Suffix Tree，但它们可能不适合文本编辑器应用程序。

Answer 2

我建议你改编一个Trie。在追加操作中，添加以新字符结尾的字符串的所有后缀，长度不超过数据结构中字符串的最大长度。在前面添加字符串的所有前缀，从新字符开始，长度不超过字符串的固定长度。渐近地，这两个操作都是常数——它们取O(k^2)其中 k 是字符串的固定长度。对于结构中的每个节点，跟踪以该节点结尾的所有字符串（可能是列表）。

搜索操作将再次保持不变：遍历字符串并输出存储在结束节点中的所有索引（如果您没有“删除树”）。

我的方法的一个缺点是内存开销（大多数时候是单词的最大长度），但是如果允许的最大字符串长度是合理的并且您只插入真实的单词（例如来自英语词典），这应该不是很大问题。