Блог пользователя atyetti9

ML Ахо-Корасик.
Автор atyetti9, 9 лет назад, По-русски

ML на 7 тесте ахо-корасик.

Вот мой код. Помогите пожалуйста. Может что добавить/убрать.

Ссылка на задачу.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

please can anyone give me code of Axo-Corasic, at e-maxx i didn't understand yet.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Можете дать ссылку на задачу?

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

std::map занимает 32 байта. У тебя их по две на каждый узел. Вместе с другими полями структура node весит 84 байта, и в массиве t их 100К — итого 8.4 мб только на массив t. Это еще не считая 100-200 тысяч динамически выделяемых узлов в красно-черном дереве самого std::map. Mожно сделать одну мапу на узел, в которой хранить struct GG{int go; int next}; или обойтись общим map для всех узлов.

map<pair<int, char>, GG> go;
for (map<pair<int, char>, GG>::iterator it = next.lower_bound(pair<int, char>(v, 0)); it != next.end() && it->first == v; ++it)
→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    что-то тяжело понимается, можете поподробнее, пожалуйста. Точнее не могу понять как это все использовать в коде. Или же можете, пожалуйста, предоставить ваш код ахо-корасика. Как вы обычно пишите его? Если не тяжело.

    → Ответить