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

Задача на суффиксный массив
Автор Kostroma, 14 лет назад, По-русски
Подскажите, пожалуйста, задачу на КФ (лучше уровня div1 C-D), в которой можно использовать суффиксный массив
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
а че в тегах деревья?:D
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    :)
    ну я набирал "суффикс" и высветился этот тэг:))))
    кстати, я на e-maxx почему-то не нашел про суффиксные деревья чего-нибудь)
    хотя это и есть суффиксный автомат наверно??
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Суффиксный автомат и суффиксное дерево весьма похожи, но все же это не одно и то же.
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Просто мне неохота Гасфилда перепечатывать, да и зачем? :)

      Разве что кодом поделиться, который всё равно не я изобретал (всё равно чисто по книжке вряд ли можно написать нормальную реализацию, не потратив на "вылизывание" с недельку :) ).

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        можно мне код в лс отослать? :)
        в ближайшее время поботаю эти деревья :)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я читал про суффиксные деревья в статье Укконена. Там все очень хорошо написано. Правда на английском.
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится
          http://e-maxx.ru/algo/ukkonen
          → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
На CF вряд ли есть больше одной-двух, тем более, чтобы были простые.
Вот несколько с других сайтов:
http://www.spoj.pl/problems/SARRAY/
UVa 719, 10526, 11107, 11512
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
timus 1393, но у меня не получилось одним суффиксным массивом.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://forums.topcoder.com/?module=Thread&threadID=627379&start=0&mc=30
Вот здесь на английском - замечательное описание, обсуждение, ссылки на еще несколько задач по теме
→ Ответить