infoarena informatica de performanta

Sorting Big Numbers using Trie-Forest based search

authors : Serban Lupulescu and Mircea Dima

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,

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].

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].

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

trie itself.

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

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

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© |
// Sorting Big Numbers using Trie-Forest based sort indexed in a STL set (Red-Black Tree)
// copyright  idea :  Serban Lupulescu
//  implementation: Mircea Dima
// Time Complexity: O(n*max_len)
// Faculty of Mathematics and Computer Science, University of Bucharest
// :D
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#define maxh 666013
#define N 10024

using namespace std;

inline int length(char a[])
{
int n=0;
while(a[n] >= '0' && a[n] <= '9') ++n;
return n;
}

struct nod { int nr; nod *next¹⁰;};

typedef nod* trie;

inline void init(trie &n)
{
n=new nod;
n->nr=0;
memset(n->next, 0, sizeof(n->next));
}

struct cmp{
bool operator()(const pair<int, trie> &a, const pair<int, trie> &b)const
{
if(a.first < b.first) return 1;
return 0;
}
};

typedef set<pair<int, trie> , cmp > Tree;
typedef set<pair<int, trie> , cmp >:: iterator Tree_it;

Tree R; // Red-Black binary search tree with key values = pointers

inline trie find(int len) // find a trie in RBTREE
{
Tree_it i= R.find(make_pair(len, (trie)0));
if(i == R.end()) return (trie) 0;
return i->second;
}

inline void insert(trie t, int len)
{
R.insert(make_pair(len, t));
}

inline void erase(trie t, int len)
{
R.erase(make_pair(len, t));
}

inline void insert(trie T,char a[], int n)
{
for(int i=0; i < n; ++i)
{
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;
memset(T->next[a[i]]->next, 0, sizeof(T->next));
}
T=T->next[a[i]]; // go down the edge
} 
++T->nr;
}

char sol[N];

inline void afis(trie T, int n)
{
for(int i=0; i < 10; ++i)
if(T->next[i])
{
sol[n]=i;

if(T->next[i]->nr)//has a number ended?
{
for(int j=1; j <= T->next[i]->nr; ++j)
{
int k;
for(k=0; k <= n && sol[k] == 0; ++k);

for(; k <= n; ++k) printf("%d", sol[k]);
printf("\n");
}
} 
afis(T->next[i], n+1);
}
}

void read()
{
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
while(!feof(stdin))
{
char a[N];
memset(a, 0, sizeof(a));
gets(a);
int n=length(a);
for(int i=0; i < n; ++i) a[i]-='0';
trie t=find(n);

if(t == 0)
{
t= new nod;
init(t);
insert(t, n);
}

insert(t, a, n);
}

for(Tree_it i = R.begin(); i != R.end(); ++i) afis(i->second, 0);

}

int main()
{
read(); 
return 0;
}

==