|
|
back to boardA way to solve this problem in java Posted by 2rf 6 Mar 2013 01:10 Initially, in one trie node i stored: Node child, sibling, sufLink; byte parSymb; short lEnd; This is 4 * 3 + 1 + 2 = 15 bytes per node, ML 28. Then I used static array of nodes(maximum number of nodes is 99991), memory consumption per node is the same(instead of Node reference we store int), ML 28. At the end, I stored child, sibling, sufLink and parSymb(we need 17 bits for each memory pointer and 8 bits for parent symbol, 17 * 3 + 8 = 59 bits in total) in one long, and lEnd in short, only 10 bytes per node, and got AC! |
|
|