文字列内の特定の文字のインデックスを追跡する最も効率的な方法は何ですか?

Question

次の文字列を例として取り上げます。

「素早い茶色のキツネ」

現時点では、quick の q は文字列のインデックス 4 (0 から始まる) にあり、fox の f はインデックス 16 にあります。ここで、ユーザーがこの文字列にさらにテキストを入力するとします。

「とても素早いこげ茶色のキツネ」

現在、q はインデックス 9 にあり、f はインデックス 26 にあります。

ユーザーが追加した文字数に関係なく、quick の元の q と fox の f のインデックスを追跡する最も効率的な方法は何ですか?

私にとって言語は重要ではありません。これはどちらかというと理論の問題なので、一般的に人気のある最新の言語に留めるようにして、好きな言語を使用してください。

私が提供したサンプル文字列は短いですが、任意のサイズの文字列を効率的に処理できる方法を期待しています。したがって、オフセットを使用して配列を更新すると、短い文字列では機能しますが、文字数が多くなると行き詰まってしまいます。

この例では文字列内の一意の文字のインデックスを探していましたが、茶色の o やキツネの o など、異なる場所にある同じ文字のインデックスも追跡できるようにしたいと考えています。したがって、検索することは問題外です。

時間とメモリの両方の効率が良くなる答えを望んでいましたが、どちらか一方を選択しなければならないとしたら、パフォーマンスの速度の方が気になります。

Answer 1

文字列があり、その文字の一部が 面白い. 。話を簡単にするために、インデックス 0 の文字が常に興味深いものであり、その文字の前に何か (番兵) を追加しないとします。（興味深い文字、前の興味深い文字までの距離）のペアを書き留めます。文字列が「+the Very Quick dark Brown Fox」で、「quick」の q と「fox」の f に興味がある場合は、次のように記述します。(+,0)、(q,10)、(f,17)。(+ 記号は番兵です。)

次に、これらをバランスのとれたバイナリ ツリーに配置します。このバイナリ ツリーでは、順番に走査することで、文字列内に出現する順序で文字のシーケンスが得られます。もうお気づきかもしれませんが、 部分和問題:ノードに (文字、距離、合計) が含まれるようにツリーを拡張します。合計は、左側のサブツリー内のすべての距離の合計です。(したがって、合計(x)=距離(左(x))+合計(左(x))。)

このデータ構造を対数時間でクエリおよび更新できるようになりました。

追加したと言うには n 文字の左側の文字 c distance(c)+=n と言うと、すべての親の合計を更新します。 c.

インデックスは何ですかと尋ねると、 c sum(c)+sum(parent(c))+sum(parent(parent(c)))+... を計算します。

Answer 2

あなたの質問は少し曖昧です - すべての手紙の最初のインスタンスを追跡したいと考えていますか?その場合、長さ 26 の配列が最良の選択肢となる可能性があります。

文字列のインデックスよりも低い位置にテキストを挿入するときは、挿入された文字列の長さに基づいてオフセットを計算するだけです。

Answer 3

また、すべてのデータ構造と対話がすべての言語で同じように効率的かつ効果的であるわけではないため、ターゲット言語を念頭に置いておくと役立ちます。

Answer 4

同様の状況で通常役立つ標準的なトリックは、文字列の文字をバランスの取れたバイナリ ツリーの葉として保持することです。さらに、ツリーの内部ノードは、特定のノードをルートとするサブツリー内で発生する文字のセット (アルファベットが小さく固定されている場合は、ビットマップである可能性があります) を保持する必要があります。

この構造への文字の挿入または削除には、O(log(N)) 操作のみが必要です (ルートへのパス上のビットマップを更新します)。また、文字の最初の出現の検索にも O(log(N)) 操作が必要です。ルート。ビットマップに興味深い文字が含まれる左端の子が表示されます。

編集：内部ノードは、文字のインデックスを効率的に計算するために、表現されたサブツリー内の葉の数も保持する必要があります。