Реализация Trie с картой
Я работал над решением проблемы сегодня. Но я застрял. Я знаю, как работает три, но проблема в том, что я знаю, как реализовать его с помощью статических массивов и классов. Сегодня, просматривая веб-страницы, я прочитал, что есть способ реализовать попытки с использованием stl :: map. Я пробовал сегодня, но я до сих пор не знаю, как вставить элементы в Int.
эта структура.
Edit1: я пытаюсь решить эту проблему: spoj.com/problems/TAP2012D
Я хочу знать, как добавить слова в три с
edit2: я знаю, как работает карта, я просто не знаю, как работает три с картой. Я хочу кого-то, кто знает о попытках.
Вот что я сделал до сих пор
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]]=
}
}
}
Решение
Узел 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 */
}
Другие решения
На мой взгляд, лучше использовать 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;
};
Конечно, может быть проблема утечек памяти с помощью узлов TrieNode, которые вы создаете с помощью нового оператора. Возможно, какой-то обход дерева (на основе DFS) для посещения всех узлов по принципу «снизу вверх» и их удаления может помочь избежать утечек памяти.
Правильный способ вставки элементов в stl :: map должен быть сделан следующим образом
std::map<char,int> M;M.insert ( std::pair<char,int>('aaa',1) );
M.insert ( std::pair<char,int>('bbb',2) );