mr146's blog

Ахо-Корасик
By mr146, 14 years ago, In Russian
Как хранить построенный бор в памяти максимально сжато?
Текущая структурка:
struct Vertex
{
     list<pair<char, int> > next;
     int link, prev, near;
     char prevc;
}v[100500];
Бор на словаре из не слов суммарной длинны не более 100000. Надо вжать в 8мб.
Как это сделать? =)
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know its late, however, I had the same problem. I tried different approaches, the best I got was using a global hash table, but this got me MLE at test 10. Did you manage to solve the problem ? If so, what was your approach ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have used one global hash table too, my solution uses only 4 MB of memory.

    → Reply