Bor

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.