Тема: Алгоритм Ахо-Корасик на сжатом боре
Пытаюсь сдать вот эту задачу на Java. К сожалению преодолеть ML на 28 тесте пока не удалось, хотя в вершине бора хранится всего лишь 3 ссылки на вершины(суффиксная, на сына и на брата), byte - символ по которому мы приходим в нашу вершину из родителя и short - самая большая длина строки, заканчивающейся в этой вершине. Итого - 3*4 + 1 + 2 = 15 байт, все образцы занимают 100 килобайт, то есть примерно 10^5 вершин бора, всего 1.5 мегабайта. Но видимо из-за всяких бяк типа garbage collector'а занимается еще дофига памяти Однако перед тем, как переписывать всё это дело на массивы хочется узнать, есть ли какие-нибудь асимптотические оптимизации для потребления памяти(типа сжатого бора. Но тогда непонятно, как хранить все суффиксные ссылки для промежуточных вершин на ребре). Ну или неасимптотические
Так же пользуясь случаем, обращу внимание публики на эту тему.