### StoneCold_'s blog

By StoneCold_, 7 years ago, Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?  Comments (16)
 » let f be the matrix representation of your trielet f[k] be the list of links for the k-th nodelet f[k][x] = m, the node who represents the son of k-th node using x-th character, m = -1 is there is not a link. int MAX = Max number of nodes int CHARSET = alphabet size int ROOT = 0 int sz = 1; f[MAX][CHARSET] void init() { fill(f, -1); } void insert(char [] s) { int node = ROOT; for (int i = 0; i < size(s); i++) { if ( f[node][ s[i] ] == -1 ) f[node][ s[i] ] = sz++; node = f[node][ s[i] ]; } } Notes: Root node is at f sz is the numbers of nodes currently in trieI guess would be easy to you implement other functions.
•  » » can you explain it by taking an example?
•  » » It is an explanation where you are storing the size of the trie ..But it is not suitable when we need to use this for finding the prefixes or calculating the xor or something like that ...Is it ???
•  » » How to mark a complete word? Using another array of same size of f? If we can't mark complete word, incomplete word will be found by searching.
 » It's my implementation of trie without using recursion and with using 2D array.
•  » » Nice code!! Thanks a lot.. Helped a lot
•  » » chrome Can you please explain your code. It would be really nice and helpful.
•  » » Thanks chrome!
•  » » thanks,,can you plz add a delete operation?
•  » » nice code :p
 » You can find it in PrinceOfPersia's blog on data structures.
 » My code hereI like this because 'add' and 'query' are in the same function (:
 » Why is this used instead of making nodes by using struct?
•  » » 14 months ago, # ^ | ← Rev. 2 →   1) because accessing values in arrays can benefit from caching while it won't be the case with struct since every node will be allocated wherever memory is available on heap(i.e. not contiguously). 2) Dynamically allocating memory on heap is slower(i.e. using new when using struct). There might be other reasons but the above are the only one's which i can think of now.
•  » » » does this have any significant benefit in competitions?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   In this problem : https://www.codechef.com/SEPT15/problems/REBXOR/ my solution using normal trie(created using dynamic allocation) failed with TLE, while other's solution using 2D trie implementation passes easily.