compressed array in Trie | question

Revision en2, by LashaBukhnikashvili, 2015-07-03 21:32:21

I'm trying to solve this problem and I am using code.

Here maximum number nodes of Trie is less than 25*1000000,But for each node I have array of 26 elements,and memory is growing up to 25*25*1000000 in worst case.I saw other codes and they are using 2 links,can't understand it,if you can,help me to understand idea of such Trie with compressed array.

P.S to use vector for each node, instead of array, then I will lost time for Build Trie(for finding some character of some node) and there should be *26 TL,and I don't want this

solved my oversight :)

Tags trie, compressed trie, 557e


  Rev. Lang. By When Δ Comment
en2 English LashaBukhnikashvili 2015-07-03 21:32:21 31 Tiny change: ' want this' -> ' want this\n\n**solved** my oversight :) '
en1 English LashaBukhnikashvili 2015-07-03 21:25:47 686 Initial revision (published)