ミニ プロジェクトとしてテキスト エディターを作成する必要があり、次の操作をサポートするデータ構造またはアルゴリズムを設計する必要があります。
O（log n）時間以下の各操作。検索と置換操作はかなりの量になりますが、必須ではありません。文字列の最大長は一定です。これを達成する方法はありますか？
ありがとう！
Trieを適応させることをお勧めします。追加操作では、新しい文字で終わる文字列のすべてのサフィックスを、データ構造内の文字列の最大長までの長さで追加します。prepend では、文字列の固定長までの長さで新しい文字から始まる文字列のすべてのプレフィックスを追加します。漸近的に、両方の操作は定数O(k^2)です。k は文字列の固定長です。構造内の各ノードについて、そのノードで終了するすべての文字列 (おそらくリスト) を追跡します。
検索操作は再び一定になります。文字列を反復処理し、終了ノードに格納されているすべてのインデックスを出力します (「ツリーを削除」していない場合)。
私のアプローチの欠点は、メモリのオーバーヘッド (ほとんどの場合、単語の最大長) ですが、許容される最大文字列長が妥当であり、(たとえば英語の辞書から) 実際の単語のみを挿入する場合、これは大きくないはずです。問題。