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

Автор fullaccepted, 13 лет назад, перевод, По-русски

Всем привет!
Недавно, я изучил алгоритм построения Суффиксного автомата с сайта e-maxx'а. Как мне кажется, я все понял.
После прорешевания некоторых задач с архивов ЛКШ я направился на онлайн жаджы. Не найдя ничего подходящего на тимусе, я перешел на КодФорсес. Задачи были успешно решены.

Но я застрял на задаче Names for Babies, пожалуйста, помогите решить ее!

На самом деле у меня проблема с построением линейной динамикой на автомате или дереве. Может ли кто дать совету по решению подобных задач? Основные приемы или что-нибудь подобное... я понял динамику немного другого типа(например Цензура на timus), но другие типы задач, как "количество различных подстрок" и "длина различных подстрок" вызывают затруднения.

В описаной выше задаче, нужно найти количество различных подстрок длиной от l до r;


Буду рад любой помощи!

[picture of bicycle here]

Я понимаю: english, русский, turkce, 中國, 한국의, Deutsch...

Шутка, я нормально понимаю первые два языка.


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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Попробуй с того же e-maxx'а полиномиальные хеши и алгоритм Рабина-Карпа Я не изучал суффиксные автоматы, но мне через хеши, кажется, это легче будет решить.

Но а если хочешь через суффиксные автоматы, то удачи =)

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Судя по ограничениям нужно это кол-во находить за линию. Тут подойдет Укконен. Построим суффиксное дерево. Далее dfs'ом пробежимся по дереву и для каждой вершины посчитаем сумму весов ребер поддерева этой вершины. Если ребро находится на глубине от l до r, то его вес 1, иначе вес 0. Ответ будет хранится в корне дерева.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, попробую написать. А можно ли это применить на суффиксном автомате?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Конечно. У него такие же переходы по символам. Просто стартуй из корня и считай глубину захода в рекурсию.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А если я буду делать рекурсией, разве я не сделаю очень большое число вызовов, которое больше линейного?
        Да и хранить результаты для каждой вершины не кажется логичным, ведь глубина меняется.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Время обхода будет O(Кол-во состояний). Т.к. автомат представляет собой деревообразую структуру, то каждое состояние мы посетим ровно 1 раз.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Разве древообразную? По-моему, это ациклический направленный граф(Directed-Acyclic-Graph) и одно состояние рекурсией мы можем посетить много раз
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну нам же не нужно переходить по суффиксным ссылкам в рекурсии. Нам нужно просто построить суффиксное дерево за O(N).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have ac the names for babies problem with n(lgn)^2 suffix array then n*(LCP of complexity lgn)=nlgn . Think like this, if 2 suffix has lcp of size l, then for distinct subset of lengths less then l, you have to considered only one of the suffix. Also for any suffix, the string which have longest LCP with it, is one of the adjacent one with it in suffix array.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Для суффиксного автомата это решается следующим образом.

Заметим, что одному состоянию автомата может соответствовать несколько строк (причём разной длины). Однако известно, что все строки, соответствующие одному состоянию - их длины образуют некоторый сплошной отрезок [a;b], причём никакая длина не повторяется дважды.

Более того, стандартный алгоритм подсчитывает это число b - оно там называется length. Число a можно найти так: перейдём из текущего состояния по суффиксной ссылке и возьмём его length + 1.

Ну и всё, мы научились узнавать для каждого состояния этот отрезок длин [a;b], теперь надо просто к ответу прибавить длину пересечения этого отрезка с отрезком [l;r].



P.S. Вообще задачи всегда проще решаются на суфф. дереве (в данном случае это тоже верно), однако из соображений скорости написания обычно предпочтительней уметь решать те же задачи с помощью суфф. автомата.

  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    То есть описанный метод в статье динамикой для подсчета количества различных строк вовсе и не нужен. Все что нужно, подсчитать число