Trie Implementation With Map

Question

Я работал над решением проблемы сегодня. Но я застрял. Я знаю, как работает trie, но проблема в том, что я знаю, как реализовать его со статическими массивами и классами. Сегодня, просматривая в Интернете, я читаю, что есть способ реализовать попытки с использованием stl :: map. Я пробовал сегодня, но я до сих пор не знаю, как вставлять элементы в int. это struchture.

Edit1: я пытаюсь решить эту проблему: spoj.com/problems/TAP2012D Я хочу знать, как добавить слова к синтаксическому дереву с EDIT2: Я знаю, как работает карта, я просто не знаю, как работает trie с картой. Я хочу, чтобы кто-то знал о попытках.

Вот что ив сделал до сих пор

const int ALPH_SIZE = 26; 
using namespace std; 

struct trie{ 
    map<char,int> M; 
    int x,y; 
    trie(); 
}; 

trie T[1000000]; 


trie::trie() 
{ 
    x=y=0; 
} 
int maximo; 


void addtrie(string palabra) 
{ 
    int tam=palabra.size(); 
    int pos=0; 
    for(int i=0;i<tam;i++) 
    { 
     if(T[pos].M.find(palabra[i])==T[pos].M.end()) 
     { 
      T[pos].M[palabra[i]]=new trie(); 
      T[pos].M[palabra[i]]= 
     } 

    } 

} 

Answer 1

A Trie узел хранит карту существующие символы и флаг, указывающий, соответствует ли узел слову в trie.

struct Node 
{ map<char, Node*> a; 
    bool flag; 

    Node() { flag = false; } 
}; 

Теперь вставка похожа на то, что вы сделали бы со статическим массивом, за исключением того, что вы используете карту здесь.

void insert(Node *x, string s) 
{ for(int i = 0; i < s.size(); i++) 
    { if(x->a.count(s[i]) == 0) 
     /* no outgoing edge with label = s[i] so make one */ 
     { x->a[ s[i] ] = new Node; 
     } 
     x = x->a[ s[i] ]; 
    } 
    x->flag = true; /* new word */ 
} 

Answer 2

Правильный способ вставить элементы в СТЛ :: карте должно быть сделано следующим образом

std::map<char,int> M; 


    M.insert (std::pair<char,int>('aaa',1)); 
    M.insert (std::pair<char,int>('bbb',2)); 

Answer 3

Использование unordered_map лучше, на мой взгляд.

struct TrieNode { 
     char c; 
     unordered_map<char, TrieNode*>links; 
     bool end; 
    }; 

    TrieNode* insert(TrieNode* root, string word) { 
     TrieNode* current = root; 

     for (auto it: word) { 
      if (current->links.find(it) == current->links.end()) { 
      TrieNode* node = new TrieNode(); // possible memory leak? 
      node->c = it; 
      node->links = {}; 
      node->end = false; 

      current->links[it] = node; 
      } 

     current = current->links[it]; 
     } 

    current->end = true; 
    return root; 
    }; 

Ofcourse, там может быть проблема наличия утечек памяти с TrieNodes, которые вы создаете с новым оператором. Может быть, какой-то обход дерева (основанный на DFS) для посещения всех узлов снизу вверх и удаления их может помочь избежать утечек памяти.