Module: Bor


Problem

1/10

Bor : le début

Theory Click to read/hide

Barre
Bor est une structure de données pour stocker un ensemble de chaînes, qui est un arbre enraciné avec des symboles sur les bords. < /div>
Chaque sommet de bore correspond à un préfixe d'une chaîne ajoutée. Ce préfixe lui-même est obtenu en écrivant séquentiellement des caractères sur les arêtes du chemin de la racine à ce sommet. En même temps, exactement un sommet correspond à chaque préfixe existant. Bor root correspond à une chaîne vide.

Exemple de bore pour {be, bee, can, cat, cd}



L'orange indique les sommets qui correspondent aux mots de l'ensemble eux-mêmes. Ils sont appelés terminaux.

Vous trouverez ci-dessous le code permettant de stocker le bore et d'y ajouter des lignes. Cette méthode stocke l'alésage à travers un tableau. Il existe également une implémentation via des pointeurs, qui est présentée dans le code de la tâche pour l'entraînement.
  // taille de l'alphabet en mots considérés const entier alpha = 26 ; // structure pour le haut du foret structure Noeud{ // vecteur d'arêtes sous forme de tableau d'adjacence, soit : // next[0] - enfant lors du saut par-dessus le caractère numéro 0 ('a') // next[1] - enfant lors du saut par-dessus le caractère numéro 1 ('b') // etc. vecteursuivant ; // Options supplémentaires // dans ce cas, la hauteur du sommet h et le drapeau de terminalité entier h ; terme booléen;; Noeud(int h) { next.resize(alph, -1); // initialement sans arêtes ceci->h = h ; // la hauteur est égale à celle spécifiée terme=faux ; // top n'est pas terminal par défaut } } ; // liste des sommets, initialement racine à hauteur nulle vecteur trie(1, nœud(0)); // fonction pour ajouter une chaîne au bore void add(const string& s) { entier v = 0 ; // numéro du sommet courant, en partant de la racine forn(je, (int)s.taille()) { int c = s[i] - 'a'; // récupère le numéro du caractère courant dans la chaîne // si la transition souhaitée n'existe pas encore, alors nous en créerons une nouvelle si (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // le nouveau numéro de sommet est   // taille de perçage actuelle (avec numérotation 0) trie.push_back(Node(trie[v].h + 1)); // crée un nouveau sommet de hauteur 1 de plus } v = trie[v].next[c] ; // se déplacer le long du bord désiré } // quand nous sommes arrivés au sommet,   // qui correspond à la chaîne entière,   // puis marquez-le comme terminal trie[v].term = vrai ; }
Si vous devez soutenir la suppression de lignes du bore, cela se révélera probablement malhonnête. Autrement dit, supprimez simplement le drapeau terminal (ou, peut-être, au lieu du drapeau, vous devrez stocker un nombre variable) et laissez l'arbre de bore lui-même inchangé.

Ainsi, les insertions/recherches/suppressions abusives fonctionnent en temps linéaire à partir de la longueur de la chaîne de requête.

Le bore lui-même, dans le pire des cas, occupera la mémoire O(n|Σ|), où n est la longueur totale de toutes les chaînes, et Σ > - l'alphabet des chaînes utilisées.

Problem

Bor est une structure de recherche d'informations efficace. Utilisez cette structure de données pour stocker et rechercher des chaînes. 

Il est nécessaire après le traitement des chaînes pour savoir si cette chaîne existe dans Bor.

Entrée
La première ligne contient un seul entier N. Sur les lignes N suivantes, des mots composés de lettres minuscules de l'alphabet latin. Ensuite un seul entier K. Sur les lignes K suivantes, des mots composés de lettres minuscules de l'alphabet latin.
 
Sortie
Imprimer pour chaque chaîne du second ensemble si elle existe dans la structure de données ("Oui")  ; ou non ("Non".
 
Exemples
4
le
un
ici
répondre
tout
par
au revoir
leur
2
le
ceci
# Entrée Sortie
1 Oui
Non

 

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++
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!