Trie Implementation With Map

Question

i was working solving a problem today. But i got stucked. I know how a trie works but the problem is that i know how to implement it with static arrays and classes. Today surfing on the web i read that there is a way to implement tries using stl::map. I tried today but i still dont know how to insert elements on int. this struchture.

Edit1: i am trying to solve this problem :spoj.com/problems/TAP2012D I want to know how to add the words in to the trie with edit2: I know how a map works, i just dont know how a trie with a map works. I want someone that knows about tries.

Here is what ive done so far

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 node stores a map of existing out characters and a flag indicating if the node corresponds to a word in the trie.

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

    Node() { flag = false; }
};

Now insertion is similar to what you'd do with a static array, except that you are using a map here.

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 */
}