字符串數據結構支持追加，前插和搜索操作

Question

我需要建立一個文本編輯器，我的小項目，我需要設計一個數據結構或者算法，支持以下操作：

• 追加：追加字符串末尾的字符。
• 前置：在字符串的開頭預先加上一個字符。
• 搜索：給定一個搜索字符串s，找到所有出現的字符串。

每個操作在O（log n）時間或更少。搜索和替換操作將顯而易見，但不是必需的。字符串的最大長度是恆定的。任何想法如何實現這一目標？

謝謝！

Answer 1

我會建議你改編一個Trie。在追加操作中，添加以新字符結尾的字符串的所有後綴，長度最大爲數據結構中字符串的最大長度。在prepend上添加從新char開始的字符串的所有前綴，長度最大爲字符串的固定長度。漸近地，兩個操作都是不變的 - 它們取O(k^2)，其中k是字符串的固定長度。對於結構中的每個節點都要跟蹤結束於該節點的所有字符串（可能是一個列表）。

搜索操作將再次保持不變：遍歷字符串並輸出存儲在結尾節點中的所有索引（如果您還沒有「退出樹」）。

我的方法的一個缺點是內存開銷（最多時候是一個單詞的最大長度），但是如果允許的最大字符串長度是合理的並且只插入真實單詞（例如從英語詞典中），則應該不是一個大問題。

Answer 2

這種應用程序的常見數據結構是Rope，其中Append和Prepend是O（1），儘管這取決於樹是否平衡。但是，正如Толя所指出的，搜索將是線性的。

確實存在可以使搜索更快的數據結構，例如Suffix Tree，但它們可能不適用於文本編輯器應用程序。