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

Question

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

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

每个操作在 O(log n) 时间内或更少。搜索和替换操作将是可观的，但不是必需的。字符串的最大长度是常数。有什么想法可以实现吗？

谢谢!

Answer 1

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

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