ボル

Bor は文字列のセットを保存するためのデータ構造であり、端にシンボルがあるルート ツリーです。 < /div>
各ボロン頂点は、追加された文字列の接頭辞に対応します。このプレフィックス自体は、ルートからこの頂点までのパス上のエッジに文字を順番に書き込むことによって取得されます。同時に、正確に 1 つの頂点が既存の各プレフィックスに対応します。B またはルートは空の文字列に対応します。

{be、bee、can、cat、cd} のホウ素の例



オレンジは、セット自体の単語に対応する頂点を示します。これらはターミナルと呼ばれます。

以下は、ボロンを保存し、それに行を追加するコードです。このメソッドは、配列を通じてボアを保存します。トレーニング用のタスクのコード内に提示されるポインターを介した実装もあります。
  // 考慮された単語のアルファベットのサイズ const int alpha = 26; // ドリルの上部の構造 構造体ノード{ // 隣接テーブル形式のエッジのベクトル、つまり次のとおりです。 // next[0] - 文字番号 0 ('a') を飛び越えるときの子 // next[1] - 文字番号 1 を飛び越えるときの子 ('b') // など ベクトル次; // 追加のオプション // この場合、頂点の高さ h と終端性のフラグ int h; ブール用語;; ノード(int h) { next.resize(alph, -1); // 最初はエッジなし this->h = h; // 高さは指定されたものと同じです 用語=偽; // デフォルトではトップはターミナルではありません } }; // 頂点のリスト、最初は高さゼロのルート ベクトル<ノード> trie(1, Node(0)); // ボロンに文字列を追加する関数 void add(const string& s) { int v = 0; // ルートから始まる現在の頂点の番号 forn(i, (int)s.size()) { int c = s[i] - 'a'; // 文字列内の現在の文字の番号を取得します // 目的のトランジションがまだ存在しない場合は、新しいトランジションを作成します if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // 新しい頂点番号は   // 現在のドリル サイズ (0 から番号付け) trie.push_back(Node(trie[v].h + 1)); // 高さ 1 の新しい頂点を作成します } v = トライ[v].next[c]; // 目的のエッジに沿って移動します } // 頂上に着いたら、   // 文字列全体と一致します。   // それをターミナルとしてマークします trie[v].term = true; }
ボロンからの行の削除をサポートする必要がある場合、それはおそらく不正であることが判明します。つまり、ターミナル フラグを削除するだけで (フラグの代わりに変数を保存する必要があるかもしれません)、ボロン ツリー自体は変更しないでください。

したがって、挿入/検索/不当な削除はクエリ文字列の長さから線形時間で動作します
。
最悪の場合、Boron 自体は O(n|Σ|) メモリを占有します。ここで、n はすべての文字列の合計長であり、Σ > - 使用される文字列のアルファベット。