Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?

# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 191 |

2 | Errichto | 184 |

3 | rng_58 | 160 |

4 | PikMike | 158 |

5 | Petr | 156 |

6 | Vovuh | 153 |

6 | Um_nik | 153 |

6 | neal | 153 |

9 | Ashishgup | 152 |

10 | majk | 151 |

10 | 300iq | 151 |

Please can anyone provide a good implementation of trie using a 2D array instead of using recursion ?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 19:26:55 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

let f be the matrix representation of your trie

let f[k] be the list of links for the k-th node

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

Notes: Root node is at f[0] sz is the numbers of nodes currently in trie

I 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?

You can find it in PrinceOfPersia's blog on data structures.

My code here

I like this because 'add' and 'query' are in the same function (: