Module: 波尔


Problem

1/10

博尔：开始

Theory Click to read/hide

酒吧
Bor是一种用于存储一组字符串的数据结构，它是一个边上有符号的有根树。 < /分区>
每个硼顶点对应于一些添加字符串的前缀。这个前缀本身是通过在从根到这个顶点的路径上的边上顺序写入字符得到的。同时，每个存在的前缀恰好对应一个顶点。 Bor根对应一个空字符串。

硼的例子 {be, bee, can, cat, cd}



橙色表示对应于集合本身的单词的顶点。它们被称为终端。

下面是存储硼​​并向其添加线条的代码。此方法通过数组存储钻孔。还有一种通过指针的实现，在训练任务的代码中给出。
  // 考虑单词的字母大小 const int alpha = 26; // 钻头顶部的结构 结构节点{ // 邻接表形式的边向量，即： // next[0] - 跳过字符号 0 ('a') 时的子节点 // next[1] - 跳过字符号 1 ('b') 时的子节点 // ETC。 向量下一个； // 额外选项 // 在这种情况下，顶点 h 的高度和终端标志 诠释 h; 布尔项；； 节点（int h）{ next.resize(alph, -1); // 最初没有边 this->h = h; // 高度等于指定的 术语=假； // top 默认不是终端 } }; // 顶点列表，初始根在零高度 矢量<节点>特里（1，节点（0））； // 向硼添加字符串的函数 void add(const string& s) { 整数 v = 0； // 当前顶点的序号，从根开始 forn(i, (int)s.size()) { int c = s[i] - 'a'; // 获取字符串中当前字符的个数 // 如果所需的转换尚不存在，那么我们将创建一个新的 如果（trie[v].next[c] == -1）{ trie[v].next[c] = (int)trie.size(); // 新的顶点号是   // 当前钻孔尺寸（带 0 编号） trie.push_back(节点(trie[v].h + 1)); // 再创建一个高度为 1 的新顶点 } v = trie[v].next[c]; // 沿着想要的边移动 } // 当我们到达顶部时，   // 匹配整个字符串，   // 然后将其标记为终端 trie[v].term = true; }
如果您需要支持从硼中删除行，那么它可能会被证明是不诚实的。也就是说，只需删除终端标志（或者，也许您需要存储一个可变数字而不是标志），并保持硼树本身不变。

因此，插入/搜索/不公平删除的工作时间与查询字符串的长度成线性关系。

Boron本身，在最坏的情况下，会占用O(n|Σ|)内存，其中n是所有字符串的总长度，Σ > - 所用字符串的字母表。

Problem

Bor 是一种高效的信息检索结构。使用此数据结构来存储和搜索字符串。 

需要在对字符串进行处理后，判断这个字符串是否存在于Bor中。

输入
第一行包含一个整数N。在接下来的 N 行中，单词由拉丁字母表的小写字母组成。接下来 一个整数K。在接下来的 K 行中，由小写的拉丁字母组成的单词。
 
输出
打印第二组中的每个字符串是否存在于数据结构中（“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
一个
那里
回答
任何
由
再见
他们的
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!