Module: Bor


Problem

1/10

Theory Click to read/hide

B.
Bor ist die Datenstruktur zur Speicherung einer Reihe von Linien, die der Wurzelbaum mit Symbolen auf den Rippen ist.

Jede Spitze der Fledermaus entspricht einem Präfix, einige hinzugefügte Linie. Dieses Präfix selbst wird durch eine konsequente Aufzeichnung der Symbole auf den Rippen von der Wurzel auf diese Oberseite erzeugt. Gleichzeitig entspricht jedes vorhandene Präfix genau einem Top. Bores Wurzel entspricht der leeren Linie.

Beispiel für {be, bee, can, cat, cd}



Die Orange ist durch die Spitzen gekennzeichnet, die den Worten des Satzes selbst entsprechen. Sie werden gerufen Terminal♪

Im Folgenden werden der Akku-Speichercode und seine Ergänzung vorgestellt. So bleibt der Kampf durch die Masse. Es gibt auch die Umsetzung durch die Indikatoren, die im Ausbildungscode dargestellt werden.
// Alphabetgröße in den zu berücksichtigenden Wörtern
const int alph = 26;

/ Struktur für das Bora-Top
struct Node{
/ Rebervektor in Form einer Kommunikationstabelle, d.h.:
- Ja.
- Ja.
- usw.
Vektor weiter;

/ Zusätzliche Parameter
// in diesem Fall die Höhe der Spitze h und die Flagge der Terminologie
int h;
boolterm;

Node(int h) {
next.resize(alph, -1); // ursprünglich ohne Rippe
Diese-teriorh = h; / Höhe gleich
Term = falsch; / standardmäßig ist das Top kein Begriff
♪
?

/ Liste der Peaks ursprünglich auf Nullhöhe
Vektor Trie(1, Node(0));

// Funktion des Hinzufügens der Zeile zum Einbruch
nichtig add(const string komponente s) {
int v = 0; / Aktuelle Top-Zahl ab Wurzel
forn(i, (int)s.size() {~}
int c = s[i] - 'a'; / erhielt die aktuelle Symbolnummer in der Zeile

/ Ist der notwendige Übergang noch nicht vorhanden, machen Sie einen neuen.
wenn (trie[v].next[c]
trie[v].next[c] = (int)trie.size(); / neue Höchstzahl gleich
/ aktuelle Batteriegröße (bei 0 Nummer)
trie.push_back(Node(trie[v].h + 1)); /
♪
v = trie[v].next[c]; //
♪

/ Als es oben war,
// die der ganzen Linie entspricht,
/ Wir markieren es als Begriff
trie[v].term = true;
♪

Wenn Sie die Entfernung des Laufs unterstützen müssen, ist es wahrscheinlich nicht fair. Ich meine, nur um die Flagge der Terminologie zu entfernen (oder vielleicht, anstelle der Flagge, wäre es notwendig, eine variable Zahl zu halten) und der Bora Baum selbst würde sich nicht ändern.

Somit wird die Versorgungs-/Detektion/Nicht-Schenkel-Entsorgung zu linearer Zeit aus der Länge der linearen Anforderung betrieben.

Bor wird im schlimmsten Fall besetzt sein. O(n|Σ|) wenn n - Gesamtlänge aller Linien, a Σ - Das Alphabet der verwendeten Zeilen.

Problem

Bor ist eine effektive Struktur, um Informationen zu finden. Verwenden Sie diese Datenstruktur, um Strings zu speichern und zu finden. 

Es ist erforderlich, nach der Verarbeitung der Zeilen herauszufinden, ob diese Zeile im Bor vorhanden ist.

Eingabe
Die erste Zeile enthält eine ganze Zahl N. Die folgenden N -Zeilen enthalten Wörter, die aus kleinen Buchstaben des lateinischen Alphabets bestehen. Als nächstes eine ganze Zahl K. Die folgenden K Zeilen enthalten Wörter, die aus kleinen Buchstaben des lateinischen Alphabets bestehen.
 
Ausgabe
Geben Sie für jede Zeile aus dem zweiten Satz aus, ob sie in der Datenstruktur vorhanden ist ("Yes") oder nicht ("No").
 
Beispiele
№ Eingabe Ausgabe
1
4
the
a
there
answer
any
by
bye
their
2
the
this
 Yes
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!