Module: Bor


Problem

1/10

Bor: Başlangıç

Theory Click to read/hide

Çubuk
Bor, kenarlarında semboller olan köklü bir ağaç olan bir dizi diziyi depolamak için kullanılan bir veri yapısıdır. < /div>
Her bir bor köşesi, bazı eklenen dizelerin bir önekine karşılık gelir. Bu ön ekin kendisi, kökten bu tepe noktasına giden yoldaki kenarlara sırayla karakterler yazılarak elde edilir. Aynı zamanda, varolan her öneke tam olarak bir tepe noktası karşılık gelir. Bor kökü, boş bir dizeye karşılık gelir.

{be, bee, can, cat, cd}
için bor örneği


Turuncu, kümedeki kelimelere karşılık gelen köşeleri gösterir. Bunlara terminaller denir.

Borun depolanması ve ona satır eklenmesi için kod aşağıdadır. Bu yöntem, deliği bir dizi aracılığıyla depolar. Eğitim için görev kodunda sunulan işaretçiler aracılığıyla bir uygulama da vardır.
  // dikkate alınan kelimelerdeki alfabe boyutu sabit int alfa = 26; // matkabın üst kısmı için yapı yapı Düğümü{ // komşuluk tablosu biçimindeki kenarların vektörü, yani: // next[0] - 0 numaralı karakterin üzerinden atlarken çocuk ('a') // next[1] - 1 numaralı karakterin üzerinden atlarken çocuk ('b') // vesaire. sonraki vektör; // Ekstra seçenekler // bu durumda, h tepe noktasının yüksekliği ve terminallik bayrağı int h; bol terim;; düğüm(int h) { next.resize(alph, -1); // başlangıçta kenarsız bu->h = h; // yükseklik belirtilene eşittir terim=yanlış; // üst varsayılan olarak terminal değildir } }; // köşelerin listesi, başlangıçta sıfır yükseklikte kök vektör trie(1, Düğüm(0)); // boruna bir dizi eklemek için fonksiyon geçersiz ekle(const string&s) { int v = 0; // kökten başlayarak geçerli tepe noktasının numarası forn(i, (int)s.size()) { int c = s[i] - 'a'; // dizedeki geçerli karakterin numarasını al // İstenen geçiş henüz mevcut değilse, yenisini yapacağız if (trie[v].sonraki[c] == -1) { trie[v].sonraki[c] = (int)trie.size(); // yeni köşe numarası   // mevcut matkap boyutu (0 numaralandırma ile) trie.push_back(Düğüm(trie[v].h + 1)); // yüksekliği 1 olan yeni bir köşe oluştur } v = trie[v].sonraki[c]; // istenen kenar boyunca ilerleyin } // zirveye ulaştığımızda,   // dizenin tamamıyla eşleşen,   // sonra terminal olarak işaretle trie[v].terim = doğru; }
Bordan satırların silinmesini desteklemeniz gerekiyorsa, muhtemelen sahtekâr olacaktır. Yani, uçbirim işaretini kaldırın (veya belki de bayrak yerine bir değişken numarası kaydetmeniz gerekir) ve boron ağacının kendisini değiştirmeden bırakın.

Böylece, ekleme/arama/haksız silme, sorgu dizesinin uzunluğundan itibaren doğrusal zamanda çalışır.

Borun kendisi, en kötü durumda, O(n|Σ|) belleğini kaplar, burada n tüm dizilerin toplam uzunluğudur ve Σ > - kullanılan dizelerin alfabesi.

Problem

Bor verimli bir bilgi erişim yapısıdır. Dizeleri depolamak ve aramak için bu veri yapısını kullanın. 

Bu stringin Bor'da var olup olmadığını öğrenmek için stringleri işledikten sonra gereklidir.

Giriş
İlk satır tek bir tamsayı içerir N. Sonraki N satırlarında Latin alfabesinin küçük harflerinden oluşan kelimeler. Sonraki tek bir tamsayı K. Sonraki K satırlarında Latin alfabesinin küçük harflerinden oluşan kelimeler.
 
Çıktı
İkinci kümedeki her dize için veri yapısında var olup olmadığını yazdırın ("Evet")  veya değil ("No".
 
Örnekler

 

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++
# Girdi Çıktı
1
4
bir
orada
cevap
herhangi bir
tarafından
güle güle
onların
2
bu
 Evet
Hayır
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!