Module: ボル


Problem

1/10

ボル: ザ・ビギニング

Theory Click to read/hide

バー
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 はすべての文字列の合計長であり、Σ > - 使用される文字列のアルファベット。

Problem

Bor は効率的な情報検索構造です。このデータ構造を使用して、文字列を保存および検索します。

文字列を処理した後、この文字列が Bor に存在するかどうかを確認するために必要です。

入力
最初の行には、単一の整数 N が含まれています。次の N 行では、ラテン アルファベットの小文字で構成される単語。次は単一の整数 K です。次の K 行では、ラテン アルファベットの小文字で構成される単語。
 
出力
2 番目のセットの各文字列がデータ構造に存在するかどうかを出力します ("Yes") またはない ("いいえ".
 
例
<頭> <本体>
 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# 入力 出力
1
4
a
あそこ
答え
任意
投稿者
さようなら
彼らの
2
これ
 はい
いいえ
Write the program below 
#include <iostream>
#include <string>
using namespace std;

const int ALPHABET_SIZE = 26;

// узел
struct TrieNode
{
  struct TrieNode *children[ALPHABET_SIZE];

  // isEndOfWord истинно, если на этой узле строка заканчивается 
  bool isEndOfWord;
};

// Возвращает новый узел
struct TrieNode *getNode(void)
{
  struct TrieNode *pNode = new TrieNode;
  pNode->isEndOfWord = false;

  for (int i = 0; i < ALPHABET_SIZE; i++)
    pNode->children[i] = NULL;

  return pNode;
}

//Вставляет новую строку
void insert(struct TrieNode *root, string key)
{
  struct TrieNode *pCrawl = root;

  for (int i = 0; i < key.length(); i++)
  {
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
      pCrawl->children[index] = getNode();

    pCrawl = pCrawl->children[index];
  }

  // помечаем последнее слово
  pCrawl->isEndOfWord = true;
}

// Поиск ключа
bool search(struct TrieNode *root, string key)
{
  struct TrieNode *pCrawl = root;

  for (int i = 0; i < key.length(); i++)
  {
    int index = key[i] - 'a';
    if (!pCrawl->children[index])
      return false;

    pCrawl = pCrawl->children[index];
  }

  return (pCrawl != NULL && pCrawl->isEndOfWord);
}

int main()
{
  struct TrieNode *root = getNode();
	         
  return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!