Олимпиадный тренинг

Задача . Бор: Начало

Задача

Темы:

Бор - это эффективная структура поиска информации. Используйте эту структуру данных для хранения и поиска строк.

Требуется после обработки строк, выяснить существует ли эта строка в Бор.

Входные данные

Первая строка содержит одно целое число N. На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Далее одно целое число K. На следующих K строках слова, состоящие из маленьких букв латинского алфавита.

Выходные данные
Выведите для каждой строки из второго набора есть ли она в структуре данных ("Yes") или нет ("No").

Примеры

№	Входные данные	Выходные данные
1	4 the a there answer any by bye their 2 the this	Yes No

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	7

Комментарий учителя

Ваш ответ

C++

Напишите программу ниже
#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; }

Напишите программу ниже

#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;
}

Загруженные файлы

Нет