Бор: Начало

Бор

Бор – это структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Для построения используется корневое дерево, где каждое ребро подписано соответсвующей буквой, а там где кончается строка надо поставить метку.

Асимпттотика поиска, добавления, удаления строки S:
O(|S|) , т.е. за длину строки.

Бор для набора строк {the, there, their, answer, any, bye}:

Task

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

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

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

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

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

Ввод	Вывод
4 the a there answer any by bye their 2 the this	Yes No

C++

Write a 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; }

Write a 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;
}

Your last submission is saved in the editor window.

Results:

Бор

All results:

Education

My Account

About us

Бор

№ 1/11 Бор: Начало

All results:

Education

My Account

About us