Module: 보르


Problem

1/10

보르: 시작

Theory Click to read/hide

바
Bor는 가장자리에 기호가 있는 루트 트리인 일련의 문자열을 저장하기 위한 데이터 구조입니다. < /사업부>
각 붕소 정점은 추가된 문자열의 접두사에 해당합니다. 이 접두사 자체는 루트에서 이 꼭짓점까지 경로의 가장자리에 문자를 순차적으로 작성하여 얻습니다. 동시에 정확히 하나의 꼭짓점이 각각의 기존 접두사에 해당합니다. Bor 루트는 빈 문자열에 해당합니다.

{be, bee, can, cat, cd}에 대한 붕소 예



주황색은 세트 자체의 단어에 해당하는 정점을 나타냅니다. 이를 터미널이라고 합니다.

아래는 붕소를 저장하고 여기에 줄을 추가하는 코드입니다. 이 방법은 배열을 통해 보어를 저장합니다. 교육용 작업 코드에 표시되는 포인터를 통한 구현도 있습니다.
  // 고려된 단어의 알파벳 크기 const int 알파 = 26; // 드릴 상단 구조 구조체 노드{ // 인접 테이블 형식의 모서리 벡터, 즉: // next[0] - 문자 번호 0('a') 위로 점프할 때의 자식 // next[1] - 문자 번호 1 위로 점프할 때의 자식('b') // 등. 벡터다음; // 추가 옵션 // 이 경우 정점 h의 높이와 종단 플래그 정수 h; 부울항;; 노드(정수 h) { next.resize(alph, -1); // 처음에는 가장자리가 없습니다. 이것->h = h; // 높이가 지정된 것과 같음 용어=거짓; // top은 기본적으로 터미널이 아닙니다. } }; // 정점 목록, 처음에는 높이가 0인 루트 vector<노드> trie(1, 노드(0)); // boron에 문자열을 추가하는 함수 void add(const string& s) { 정수 V = 0; // 루트부터 시작하여 현재 정점의 번호 forn(i, (int)s.size()) { int c = s[i] - 'a';; // 문자열에서 현재 문자의 번호를 얻습니다. // 원하는 전환이 아직 존재하지 않으면 새 전환을 만듭니다. if (trie[v].next[c] == -1) { trie[v].next[c] = (int)trie.size(); // 새로운 정점 번호는   // 현재 드릴 크기(0 번호 지정) trie.push_back(노드(trie[v].h + 1)); // 높이가 1 더 높은 새 정점을 만듭니다. } v = 트리[v].다음[c]; // 원하는 가장자리를 따라 이동 } // 정상에 도달했을 때,   // 전체 문자열과 일치하는   // 그런 다음 터미널로 표시 trie[v].term = 참; }
붕소에서 행 삭제를 지원해야 하는 경우 부정직한 것으로 판명될 수 있습니다. 즉, 단순히 터미널 플래그를 제거하고(또는 플래그 대신 변수 번호를 저장해야 할 수도 있음) 붕소 트리 자체를 변경하지 않은 상태로 둡니다.

따라서 삽입/검색/불공정 삭제는 질의 문자열의 길이부터 직선적으로 작용한다.

최악의 경우 Boron 자체는 O(n|Σ|) 메모리를 차지합니다. 여기서 n은 모든 문자열의 총 길이이고 Σ > - 사용된 문자열의 알파벳.

Problem

Bor는 효율적인 정보 검색 구조입니다. 이 데이터 구조를 사용하여 문자열을 저장하고 검색합니다. 
<사업부>
이 문자열이 Bor에 존재하는지 확인하기 위해 문자열을 처리한 후 필요합니다.

입력
첫 번째 줄에는 단일 정수 N이 포함됩니다. 다음 N 줄에는 라틴 알파벳의 소문자로 구성된 단어. 다음은 단일 정수 K입니다. 다음 K 줄에는 라틴 알파벳의 소문자로 구성된 단어.
 
출력
데이터 구조에 존재하는지 여부("예")  여부("아니오".
 
예
<헤드> <몸>
 

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++
# 입력 출력
1 <사업부>4
a
거기
답변
모든
작성
안녕
그들의
<사업부>2
이
 예
아니요
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!