Module: Bor


Problem

1/10

Bor: Sự khởi đầu

Theory Click to read/hide

Thanh
Bor là cấu trúc dữ liệu để lưu trữ một tập hợp các chuỗi, là một cây có gốc với các ký hiệu trên các cạnh. < /div>
Mỗi đỉnh boron tương ứng với một tiền tố của một số chuỗi được thêm vào. Bản thân tiền tố này có được bằng cách viết tuần tự các ký tự trên các cạnh trên đường đi từ gốc đến đỉnh này. Đồng thời, chính xác một đỉnh tương ứng với mỗi tiền tố hiện có. Gốc Bor tương ứng với một chuỗi rỗng.

Ví dụ boron cho {be, bee, can, cat, cd}



Màu cam biểu thị các đỉnh tương ứng với các từ trong tập hợp. Chúng được gọi là thiết bị đầu cuối.

Dưới đây là mã để lưu trữ boron và thêm các dòng vào nó. Phương thức này lưu lỗ khoan thông qua một mảng. Ngoài ra còn có một triển khai thông qua con trỏ, được trình bày trong mã của nhiệm vụ dành cho đào tạo.
  // kích thước bảng chữ cái trong các từ được xem xét const int alpha = 26; // cấu trúc cho đỉnh của máy khoan nút cấu trúc { // vectơ các cạnh ở dạng bảng kề, nghĩa là: // next[0] - con khi nhảy qua ký tự số 0 ('a') // next[1] - con khi nhảy qua ký tự số 1 ('b') // vân vân. véc tơtiếp theo; // Tùy chọn thêm // trong trường hợp này, chiều cao của đỉnh h và cờ của thiết bị đầu cuối inth; thuật ngữ bool;; Nút (int h) { next.resize(alph, -1); // ban đầu không có cạnh này->h = h; // chiều cao bằng với quy định thuật ngữ = sai; // top không phải là terminal theo mặc định } }; // danh sách các đỉnh, ban đầu gốc ở độ cao bằng không vector trie(1, Nút(0)); // hàm thêm chuỗi vào boron void add(const string& s) { int v = 0; // số đỉnh hiện tại, bắt đầu từ gốc forn(i, (int)s.size()) { int c = s[i] - 'a'; // lấy số ký tự hiện tại trong chuỗi // nếu quá trình chuyển đổi mong muốn chưa tồn tại, thì chúng tôi sẽ tạo một quá trình chuyển đổi mới if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // số đỉnh mới là   // kích thước mũi khoan hiện tại (có đánh số 0) trie.push_back(Nút(trie[v].h + 1)); // tạo 1 đỉnh mới có chiều cao thêm 1 } v = trie[v].next[c]; // di chuyển dọc theo cạnh mong muốn } // khi chúng tôi lên đến đỉnh,   // khớp với toàn bộ chuỗi,   // sau đó đánh dấu nó là thiết bị đầu cuối trie[v].term = true; }
Nếu bạn cần hỗ trợ xóa các hàng khỏi boron, thì có lẽ nó sẽ trở nên không trung thực. Nghĩa là, chỉ cần xóa cờ đầu cuối (hoặc, có lẽ, thay vì cờ, bạn sẽ cần lưu trữ một số thay đổi) và giữ nguyên bản thân cây boron.

Do đó, thao tác chèn/tìm kiếm/xóa không công bằng hoạt động theo thời gian tuyến tính tính từ độ dài của chuỗi truy vấn.

Trong trường hợp xấu nhất, bản thân boron sẽ chiếm bộ nhớ O(n|Σ|), trong đó n là tổng độ dài của tất cả các chuỗi và Σ > - bảng chữ cái của các chuỗi được sử dụng.

Problem

Bor là một cấu trúc truy xuất thông tin hiệu quả. Sử dụng cấu trúc dữ liệu này để lưu trữ và tìm kiếm chuỗi. 

Sau khi xử lý chuỗi, cần tìm hiểu xem chuỗi này có tồn tại trong Bor hay không.

Đầu vào
Dòng đầu tiên chứa một số nguyên duy nhất N. Trên các dòng N tiếp theo, các từ bao gồm các chữ cái nhỏ trong bảng chữ cái Latinh. Tiếp theo một số nguyên K. Trên các dòng K tiếp theo, các từ bao gồm các chữ cái nhỏ trong bảng chữ cái Latinh.
 
Đầu ra
In cho từng chuỗi từ tập hợp thứ hai xem nó có tồn tại trong cấu trúc dữ liệu ("Yes")  hay không ("Không".
 
Ví dụ
<đầu>
 

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++
# Đầu vào Đầu ra
1
4
the
a
ở đó
câu trả lời
bất kỳ
bởi
tạm biệt
của họ
2
the
cái này
 Có
Không
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!