h1. Sorting Big Numbers using Trie-Forest based sort
h2. authors : Serban Lupulescu and Mircea Dima
 

Sorting Big Numbers using Trie-Forest based search
 
authors : Serban Lupulescu and Mircea Dima

h3. The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

h3. trie H[N], where H[i] is a trie with height i so when we insert a string with length i, we insert it in H[i].

The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

h3. But what happens when we have, say 2 strings, one of length 3, and one with length 10^20^? We can't declare H[10^20^].

trie H[N], where H[i] is a trie with height i so when we insert a string with lenght i, we insert it in H[i].

h3. Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

But what happens when we have, say 2 strings, one of length 3, and one with length 10^20? We can't declare H[10^20].

h3. trie itself.

Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

h3. Now if we have a string with length h we have 2 possibilities:

trie itself.

h3. 1) if there is a trie with height h in the binary search tree, we insert the string in that trie

Now if we have a string with length h we have 2 possibilities:

h3. 2) if there isn't a trie with height h in the binary search tree, we create it, we insert the string in an empty trie, and then we insert the trie in

1) if there is a trie with height h in the binary search tree, we insert the string in that trie

h3. the binary search tree.

2) if there isn't a trie with height h in the binary search tree, we create it, we insert the string, and then we insert the trie in
the binary search tree.

== code(c) |

// Sorting Big Numbers using Trie-Forest based sort indexed in a STL set (Red-Black Tree)

// copyright(c) Serban Lupulescu & Mircea Dima

// copyright   idea :          Serban Lupulescu
//             implementation: Mircea Dima

// Time Complexity: O(n*max_len)
// Faculty of Mathematics and Computer Science, University of Bucharest
// :D

#include <string>
#include <set>
#include <vector>

#define maxh 666013

#define N 10024
using namespace std;

      return n;
}

struct nod { int nr; nod *next[10];};
typedef nod* trie;

{
      for(int i=0; i < n; ++i)
      {

            if(T->next[a[i]] == 0) //if I don't have an edge, I create it

            if(T->next[a[i]] == 0)
            //if I don't have an edge, I creat it

            {
                  T->next[a[i]]=new nod;
                  T->next[a[i]]->nr=0;

            {
                  sol[n]=i;

                  if(T->next[i]->nr)//has a number ended here?

                  if(T->next[i]->nr)//has a number ended?

                  {
                        for(int j=1; j <= T->next[i]->nr; ++j)
                        {

      read();
      return 0;
}

==