Изменения
Нет описания правки
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
# Свести задачу RMQ к задаче LCA линейного размера (указание: использовать декартово дерево)
# Докажите, что число различных как строки подстрок $s$ равно $n(n + 1) / 2$ - sum(lcp[i]).
# Найти самую длинную строку $p$, такую, что она входит в строку $t$ дважды и не пересекаясь. Решение должно работать за $SA + O(n)$, где $SA$ - время построения суффиксного массива.
# Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $SA + O(n)$
# Пусть в алфавите есть ровно два символа. Построить такую строку $s$, что её суффиксный массив совпадает с данным, за $O(n)$.
# Обобщить алгоритм поиска наибольшей общей подстроки, если дано $k$ строк. Указание: используйте очередь c операцией минимум. Время работы равно $SA + O(\sum |p_i|)$, где $p_1$, $p_2$, ..., $p_k$ - заданные строки.
# Пусть $B(S)$ - бордеров $S$. Найти за $SA + O(n)$ сумму $\sum\limits_{i = 1}^{n} \sum\limits_{j = i}^{n} B(S[i..j])$.
# Найти строку над алфавитом $\{0, 1\}$, в которой $\Omega(n^2)$ различных как строки подстрок.
# Строка $s$ называется ветвящейся вправо в $t$, если существуют символы $c$ и $d$, такие что $c \ne d$ : $sc$ и $sd$ - подстроки $t$. Аналогично, ветвящаяся влево, если $cs$ и $ds$ - подстроки $t$. Найти самую длинную ветвящуюся влево и вправо подстроку $t$ за $SA + O(n)$.
# Найти количество ветвящихся влево и вправо строк для строки $t$. Считать только разные строки.
# Строка $s$ называется максимальным повтором в $t$, если 1) $s$ входит в $t$ не менее двух раз; 2) если $r$ входит в $t$ не менее двух раз, то $s$ - не является собственной подстрокой $r$. Доказать или опровергнуть, что все максимальные повторы равны по длине.
# Найти все максимальные повторы за $O(SA + n + ans)$.
</wikitex>
