Module: Bor


Problem

1/10

Bor: L'inizio

Theory Click to read/hide

Barra
Bor è una struttura dati per memorizzare un insieme di stringhe, che è un albero con radici e simboli sui bordi. < /div>
Ogni vertice di boro corrisponde a un prefisso di qualche stringa aggiunta. Questo stesso prefisso si ottiene scrivendo in sequenza i caratteri sui bordi del percorso dalla radice a questo vertice. Allo stesso tempo, esattamente un vertice corrisponde a ciascun prefisso esistente. Bor root corrisponde a una stringa vuota.

Esempio di boro per {be, bee, can, cat, cd}



L'arancione indica i vertici che corrispondono alle parole dell'insieme stesso. Si chiamano terminali.

Di seguito è riportato il codice per conservare il boro e aggiungere linee ad esso. Questo metodo memorizza il foro attraverso un array. Esiste anche un'implementazione tramite puntatori, che viene presentata nel codice dell'attività per l'addestramento.
  // dimensione dell'alfabeto nelle parole considerate const int alfa = 26; // struttura per la parte superiore del trapano struct Nodo{ // vettore di spigoli sotto forma di tabella di adiacenza, ovvero: // next[0] - bambino quando si salta sul carattere numero 0 ('a') // next[1] - bambino quando si salta sul carattere numero 1 ('b') // eccetera. vettoresuccessivo; // Opzioni aggiuntive // in questo caso, l'altezza del vertice h e il flag di terminalita' int h; termine bool;; Nodo(int h) { next.resize(alph, -1); // inizialmente senza spigoli questo->h = h; // l'altezza è uguale a quella specificata termine=falso; // top non è il terminale per impostazione predefinita } }; // elenco di vertici, inizialmente root ad altezza zero vettore trie(1, Nodo(0)); // funzione per aggiungere una stringa al boro void add(const string& s) { intero v = 0; // numero del vertice corrente, partendo dalla radice forn(i, (int)s.size()) { int c = s[i] - 'a'; // ottiene il numero del carattere corrente nella stringa // se la transizione desiderata non esiste ancora, ne creeremo una nuova if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // il nuovo numero di vertice è   // dimensione del trapano corrente (con numerazione 0) trie.push_back(Node(trie[v].h + 1)); // crea un nuovo vertice con altezza 1 in più } v = trie[v].next[c]; // si sposta lungo il bordo desiderato } // quando siamo arrivati ​​in cima,   // che corrisponde all'intera stringa,   // quindi contrassegnalo come terminale trie[v].term = vero; }
Se hai bisogno di supportare l'eliminazione delle righe dal boro, probabilmente si rivelerà disonesto. Cioè, rimuovi semplicemente il flag terminale (o, forse, invece del flag, dovrai memorizzare un numero variabile) e lascia invariato l'albero di boro stesso.

Pertanto, inserimento/ricerca/cancellazione scorretta funzionano in tempo lineare dalla lunghezza della stringa di query.

Lo stesso boro, nel peggiore dei casi, occuperà O(n|Σ|) memoria, dove n è la lunghezza totale di tutte le stringhe, e Σ > - l'alfabeto delle stringhe utilizzate.

Problem

Bor è un'efficiente struttura di recupero delle informazioni. Utilizza questa struttura dati per archiviare e cercare stringhe. 

È necessario dopo l'elaborazione delle stringhe per scoprire se questa stringa esiste in Bor.

Input
La prima riga contiene un singolo numero intero N. Nelle successive righe N, parole costituite da lettere minuscole dell'alfabeto latino. Successivamente un singolo numero intero K. Nelle successive righe K, parole costituite da lettere minuscole dell'alfabeto latino.
 
Uscita
Stampa per ogni stringa del secondo set se esiste nella struttura dati ("Yes")  oppure no ("No".
 
Esempi
# Input Uscita
1
4
il
a
qui
rispondi
qualsiasi
di
ciao
loro
2
il
questo
 Sì
No

 

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!