Дистанционная подготовка: Задача из тимуса 1590 Шифр Бэкона
Задача из тимуса 1590 Шифр Бэкона
от Роман Захаров - Четверг 15 Ноябрь 2007, 01:18
  Помогите пожалуйста задача из тимуса вот ссылка на условие
http://acm.timus.ru/problem.aspx?space=1&num=1590
а вот само условие:

Программисту Васе не повезло — вместо отпуска его послали в командировку, на научную конференцию. Надо повышать уровень знаний, сказал начальник, важная конференция по криптографии, проводится во Франции — а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета.

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

Один из докладчиков, в очередной раз пытаясь разгадать шифры Бэкона, выдвинул гипотезу, что ключ к тайнам Бэкона можно подобрать, проанализировав все возможные подстроки произведений Бэкона. «Но их же слишком много!» — вслух удивился Вася. «Нет, не так уж и много!» — закричал докладчик — «подсчитайте и вы сами убедитесь!».

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

Исходные данные

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

Результат

Выведите количество различных подстрок этой строки.

Пример

исходные данные
результат
aaba
8

Я думал так ну коль здесь надо найти количество различных подстрок данной строки то пользуемся первой частью алгоритма КМП префикс функцией там на тех местах где 0 будет не совпад. подстрока потом отщепляем первую букву от строки и повторяем наш алгоритм, но тут получилось вроде нне очень хорошо наши нули начинают пересекаться ну т.е. для разных строк 0-ли получаем для одних и тех же подстрок поэтому как то плохо Грустный как обойти это я так и не придумал, но говорят люди они сдавали таким алгоритмом(ну т.е. при помощи префикс функции) подскажите пожалуйста!

Re: Задача из тимуса 1590 Шифр Бэкона
от Борис Василевский - Суббота 17 Ноябрь 2007, 16:21
  Есть два решения.

Первое (с помощью префикс-функции).
Пусть мы знаем ответ для строки S длины (N - 1). За O(N) научимся узнавать ответ для строки (cS), то есть обновлять ответ после приписывания к строке слева какого-нибудь символа. После этого решение будет состоять из N шагов, на каждом из которых к текущей строке (которая сначала пуста) приписывается i-й (i = N, ..., 1) символ исходной строки.

Обсудим общий шаг (как вычислять ответ после приписывания). Построим префикс-функцию строки cS. После этого будем искать строку cS в строке S алгоритмом КМП. На k-м шаге будет вычисляться j = маскимальное совпадение префиксов строки cS и S[k..N],. Поэтому j-й префикс строки cS уже посчитан на предыдущих шагах и его не надо учитывать. Все остальные префиксы не встречались ранее и их надо посчитать.


Второе решение (с помощью суффискного дерева).
Именно эта задача, только под назанием "Жужжащий профессор", была дана на Зимних сборах-2005, так что в случае чего можно скачать тесты и решения.

Из всех суффиксов S[1..N], S[2..N], ..., S[N..N] строки S построим сжатый бор (такой бор называется суффискным деревом). Благодаря небольшим ограничениям, можно строить наивно за квадрат. После этого ответ -- это поличество позиций в дереве (то есть количество вершин, которое получится, если "разжать" бор).

Re: Задача из тимуса 1590 Шифр Бэкона
от Роман Захаров - Воскресенье 18 Ноябрь 2007, 21:32
  Вы писали:
"Второе решение (с помощью суффискного дерева).
Именно эта задача, только под назанием "Жужжащий профессор", была дана на Зимних сборах-2005, так что в случае чего можно скачать тесты и решения.

Из всех суффиксов S[1..N], S[2..N], ..., S[N..N] строки S построим сжатый бор (такой бор называется суффискным деревом). Благодаря небольшим ограничениям, можно строить наивно за квадрат. После этого ответ -- это поличество позиций в дереве (то есть количество вершин, которое получится, если "разжать" бор)."

Но к сожалению я очень плохо знаком с суфиксными деревьями не моглибы вы мне посоветовать что можно и где почитать(самое главное что б там понятно написано было) и задачи на эту тему желательно пока с разборами заранее спасибо!