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

Задачи на префиксное дерево(бор)
Автор Scorpy, 14 лет назад, По-русски
Подскажите, пожалуйста, какие-нибудь задачи на префиксное дерево. Очень часто встречаю упоминания о нём в различных обсуждениях, но примера задачи не нашел.
Заранее, спасибо!
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://acm.timus.ru/problem.aspx?space=1&num=1269
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На первый взгляд можно вполне решить эту задачу и хэшами!
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    это конечно бор, но уже более специфичная задача, на алгоритм Ахо-корасик. на народ.ру была неплохая статья о нем.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Статья про Ахо-Карасика есть на e-maxx.ru. И там объясняется про бор.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Для новичка лучше сначала две несложные задачи.
Посчитать кол-во различных подстрок у строки длиной n=1000. Это обычный бор.
И таже самая задача n=10000. Сжатый бор.

А дальше уже Ахо-Корасик по ссылке Nyatl.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    поясни пожалуйста как решать такую задачу бором, и как нам поможет сжатый бор?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Складываем все суффиксы строчки в бор и считаем кол-во вершин в дереве. А сжатый бор нужен, чтобы сократить память.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И та же задача n=100000. Алгоритм Укконена :)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://contests.snarknews.info/files/snss10/probs/day3.pdf
Вторая задача. Хотя можно и хэшами.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ещё задача K с NEERC 2008.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А эта задача на хеш, я на контесте написал, на нирке я набажил в порядке следования условий if
    меняем местами и решение получает ОК.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Кому на хеш, а кому и красиво решить. Ну, собственно, "мы" это уже "где-то" обсуждали, начиная отсюда :)
      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://acm.timus.ru/problem.aspx?space=1&num=1542

→ Ответить