Всем привет!
Недавно, я изучил алгоритм построения Суффиксного автомата с сайта e-maxx'а. Как мне кажется, я все понял.
После прорешевания некоторых задач с архивов ЛКШ я направился на онлайн жаджы. Не найдя ничего подходящего на тимусе, я перешел на КодФорсес. Задачи были успешно решены.
Но я застрял на задаче Names for Babies, пожалуйста, помогите решить ее!
На самом деле у меня проблема с построением линейной динамикой на автомате или дереве. Может ли кто дать совету по решению подобных задач? Основные приемы или что-нибудь подобное... я понял динамику немного другого типа(например Цензура на timus), но другие типы задач, как "количество различных подстрок" и "длина различных подстрок" вызывают затруднения.
В описаной выше задаче, нужно найти количество различных подстрок длиной от l до r;
Буду рад любой помощи!
[picture of bicycle here]
Я понимаю: english, русский, turkce, 中國, 한국의, Deutsch...
Шутка, я нормально понимаю первые два языка.
Попробуй с того же e-maxx'а полиномиальные хеши и алгоритм Рабина-Карпа Я не изучал суффиксные автоматы, но мне через хеши, кажется, это легче будет решить.
Но а если хочешь через суффиксные автоматы, то удачи =)
Судя по ограничениям нужно это кол-во находить за линию. Тут подойдет Укконен. Построим суффиксное дерево. Далее dfs'ом пробежимся по дереву и для каждой вершины посчитаем сумму весов ребер поддерева этой вершины. Если ребро находится на глубине от l до r, то его вес 1, иначе вес 0. Ответ будет хранится в корне дерева.
Да и хранить результаты для каждой вершины не кажется логичным, ведь глубина меняется.
Для суффиксного автомата это решается следующим образом.
Заметим, что одному состоянию автомата может соответствовать несколько строк (причём разной длины). Однако известно, что все строки, соответствующие одному состоянию - их длины образуют некоторый сплошной отрезок [a;b], причём никакая длина не повторяется дважды.
Более того, стандартный алгоритм подсчитывает это число b - оно там называется length. Число a можно найти так: перейдём из текущего состояния по суффиксной ссылке и возьмём его length + 1.
Ну и всё, мы научились узнавать для каждого состояния этот отрезок длин [a;b], теперь надо просто к ответу прибавить длину пересечения этого отрезка с отрезком [l;r].
P.S. Вообще задачи всегда проще решаются на суфф. дереве (в данном случае это тоже верно), однако из соображений скорости написания обычно предпочтительней уметь решать те же задачи с помощью суфф. автомата.
То есть описанный метод в статье динамикой для подсчета количества различных строк вовсе и не нужен. Все что нужно, подсчитать число