Module: بور


Problem

1/10

Bor: البداية

Theory Click to read/hide

شريط
Bor هو بنية بيانات لتخزين مجموعة من السلاسل ، وهي شجرة متجذرة برموز على الحواف. & nbsp؛ < / div>
يتوافق كل رأس بورون مع بادئة من سلسلة مضافة. يتم الحصول على هذه البادئة نفسها عن طريق كتابة الأحرف بالتسلسل على الحواف على المسار من الجذر إلى هذا الرأس. في نفس الوقت ، رأس واحد بالضبط يتوافق مع كل بادئة موجودة. & nbsp ؛ جذر بور يتوافق مع سلسلة فارغة.

مثال البورون لـ {be، bee، can، cat، cd}



يشير البرتقالي إلى الرؤوس التي تتوافق مع الكلمات من المجموعة نفسها. يطلق عليهم محطات .

يوجد أدناه رمز تخزين البورون وإضافة خطوط إليه. هذه الطريقة تخزن التجويف من خلال مصفوفة. هناك أيضًا تنفيذ من خلال المؤشرات ، والذي يتم تقديمه في رمز مهمة التدريب.
نبسب ؛ // حجم الأبجدية في الكلمات المدروسة const int alpha = 26 ؛ // هيكل الجزء العلوي من الحفر عقدة البنية { // متجه الحواف في شكل جدول مجاور ، أي: // التالي [0] - الطفل عند القفز فوق الحرف رقم 0 (& # 39 ؛ a & # 39 ؛) // التالي [1] - الطفل عند القفز فوق الحرف رقم 1 (& # 39 ؛ b & # 39 ؛) // إلخ. ناقلات التالي ؛ // خيارات اضافية // في هذه الحالة ، ارتفاع الرأس h وعلم النهايات ح ح مصطلح منطقي ؛؛ العقدة (ح ح) { next.resize (alph، -1) ؛ // في البداية بدون حواف هذا- & GT ؛ ح = ح ؛ // الارتفاع يساوي المحدد المصطلح = خطأ ؛ // أعلى ليس محطة بشكل افتراضي } } ؛ // قائمة الرؤوس ، الجذر مبدئيًا عند ارتفاع صفر متجه <عقدة> ثلاثي (1 ، عقدة (0)) ؛ // وظيفة لإضافة سلسلة إلى البورون إضافة باطلة (سلسلة ثابتة & أمبير ؛ ق) { كثافة العمليات = 0 ؛ // رقم الرأس الحالي ، بدءًا من الجذر forn (i، (int) s.size ()) { int c = s [i] - & # 39 ؛ a & # 39 ؛؛ // احصل على رقم الحرف الحالي في السلسلة // إذا لم يكن الانتقال المطلوب موجودًا بعد ، فسنقوم بعمل انتقال جديد إذا (trie [v] .next [c] == -1) { trie [v] .next [c] = (int) trie.size () ؛ // رقم الرأس الجديد هو نبسب ؛ // حجم الحفر الحالي (مع 0 ترقيم) trie.push_back (عقدة (trie [v] .h + 1)) ؛ // أنشئ قمة جديدة بارتفاع 1 أكثر } v = trie [v] .next [c] ؛ // تحرك على طول الحافة المرغوبة } // عندما وصلنا إلى القمة ، نبسب ؛ // الذي يطابق السلسلة بأكملها ، نبسب ؛ // ثم ضع علامة عليها كمحطة طرفية trie [v] .term = صحيح ؛ }
إذا كنت بحاجة إلى دعم حذف الصفوف من البورون ، فمن المحتمل أن يتضح أنه غير أمين. أي ببساطة قم بإزالة العلم الطرفي (أو ، ربما ، بدلاً من العلم ، ستحتاج إلى تخزين رقم متغير) ، وترك شجرة البورون نفسها دون تغيير.

وبالتالي ، فإن الإدراج / البحث / الحذف غير العادل يعمل في الوقت الخطي من طول سلسلة الاستعلام.

سيشغل البورون نفسه ، في أسوأ الأحوال ، ذاكرة O (n | & Sigma؛ |) ، حيث يمثل n الطول الإجمالي لجميع السلاسل ، و & Sigma؛ > - أبجدية السلاسل المستخدمة.

Problem

Bor هي بنية فعالة لاسترجاع المعلومات. استخدم بنية البيانات هذه لتخزين السلاسل والبحث فيها. & nbsp؛

مطلوب بعد معالجة السلاسل لمعرفة ما إذا كانت هذه السلسلة موجودة في Bor.

إدخال
يحتوي السطر الأول على عدد صحيح واحد N . في سطور N التالية ، تتكون الكلمات من أحرف صغيرة من الأبجدية اللاتينية. التالي & nbsp ؛ عدد صحيح واحد K . على سطور K التالية ، تتكون الكلمات من أحرف صغيرة من الأبجدية اللاتينية.
نبسب ؛
الإخراج
طباعة لكل سلسلة من المجموعة الثانية سواء كانت موجودة في بنية البيانات (" نعم ") & nbsp؛ أم لا (" لا ".
نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1
4
ال
أ
هناك
إجابة
أي
بواسطة
وداعا
بهم
2
ال
هذا
نعم
لا

نبسب ؛

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!