我需要构建一个文本编辑器作为我的迷你项目，我需要设计一个支持以下操作的数据结构或算法:
- Append : 在字符串末尾追加一个字符。
- Prepend : 在字符串开头添加一个字符。
- 搜索:给定一个搜索字符串 s，找到该字符串的所有出现。
每个操作在 O(log n) 时间内或更少。搜索和替换操作将是可观的，但不是必需的。字符串的最大长度是常数。有什么想法可以实现吗？
谢谢!
最佳答案
此类应用程序的常见数据结构是 Rope ，其中 Append 和 Prepend 是 O(1)，尽管这在一定程度上取决于树是否平衡。然而，正如 Толя 所指出的，搜索将是线性的。
肯定有一些数据结构可以使搜索更快，例如 Suffix Tree , 但它们可能不适合文本编辑器应用程序。
关于支持附加、前置和搜索操作的字符串数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15895689/