Разбираясь с тандемными повторами при решении задачи, которую обсуждали тут, я перечитал несколько трудов Гасфилда и Крочемора (не уверен что это так пишется по русски =) ) по тандемным повторам. В основном все алгоритмы, описанные там, находят все вхождения тандемных повторов в строку (примитивных, вообще всех, различных, вариаций много). И лишь только в одной статье Гасфилда отдаленно упоминается, что существует алгоритм, который отвечает для позиции i в строке, существует ли какой-нибудь (возможно минимальный) тандемный повтор начинающийся в позиции   i - L + 1 длины L. Кто-нибудь что-нибудь слышал о подобном алгоритме, статье где его можно прочитать? Или может быть кто-нибудь знает как свести одну из вышеперечисленных решенных задач к этой за приемлемое время? 

На одной из тренировок школьников на NEERC в этом году, была одна интересная строковая задача. Вот её приблизительное условие:

Помнится мне на разборе задач полуфинала Petr объяснял все задачи пользуясь презентацией или чем то подобным, кто нибудь знает где можно эту презентацию достать? 

Собственно задача состоит в следующем, есть строка зашифрованная по RLE, т.е. представленная в виде (x₁)k₁(x₂)k₂...(x_n)k_n, где (x_i)k_i означает строку из символов k_i длины x_i (например строку AAABBCCC можно представить в виде (3)A(2)B(3)C). Нужно отвечать на запросы Q_i, вывести Prefix(Q_i). (Prefix(i) - префикс функция i-го префикса строки). 

    Наверное затронутая тема стара как наш с вами мир, но на кодифорсес (до сегодняшнего дня ничего подобного я не видел. 

Как то раз, на одном TCM контестов (или что-то в этом роде), встречалась следующая задача: Дано логическое выражение с переменными, нужно его так преобразовать, чтобы получить минимальное по длине эквивалентное ему выражение. Хотелось бы узнать как решать подобную задачу? Может кто-нибудь знает статьи или классические алгоритмы решения такой задачи?

На одной из прошлых тренировок ИТМО я наткнулся на одну интересную задачу. В ней давалась строка и делались следующие запросы, перевернуть отрезок с L по R, найти LCP двух суффиксов i, j, длина строки 10⁶, да и запросов тоже 10⁵. На контесте тогда я не успел добраться до нее, заступорился на более простых задачах, а в дорешивании не смог придумать как решать. Подозрительное слово переворот так и напрашивает декартово дерево из хешей, но как его поддерживать не очень понятно =)

Задача предложена Раховым Артемом (RAD.).