Изменения
Нет описания правки
# Вычислить $z$-функцию по префикс функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
# Вычислить префикс функцию по $z$-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
# Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
# Разработайте алгоритм удаления строки из бора. После удаления бор не должен иметь "мертвых" поддеревьев, в которых нет помеченных вершин.
# Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
# Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
# Найти число вхождений каждого из образцов в тексте за время O(длина текста + постр. автомата).
# Найти последние вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата). Текст подается по одному символу слева направо и у вас нет памяти, чтобы его сохранить.
# Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
# Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)
# Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
# То же, что и в предыдущем задании, но для каждого фиксированного $i$ надо научиться получать строку с нуля за $O(|s|)$.
# Тандемный повтор - строка вида $a = bb$. Найти максимальный тандемный повтор за $O(n \log n)$, используя результат предыдущего задания. Указание: используйте алгоритм вида "разделяй и властвуй", разделите строку пополам, ответ либо лежит слева от точки деления, либо справа, либо пересекает ее.
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
# Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
# Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос).
# Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" $O(n)$ - предобработка, $O(1)$ - ответ на запрос).
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано дерево. Разбить вершины его на множество путей (каждая вершина принадлежит ровно одному пути), чтобы путь от любой вершины до любой переходил с одного пути на другой не более $O(\log n)$ раз.
# Дано дерево. Рассмотрим покрытие его вершин путями по следующему алгоритму: из каждой нелистовой вершины включаем в множество ребро в наиболее глубокое поддерево. Решает ли этот алгоритм предыдущую задачу? Если нет, то какую точную оценку можно дать на число смены текущего пути?
# Дано взвешенное дерево. Уметь отвечать на запросы "минимальное ребро на пути из $u$ в $v$" и "изменить весь ребра $uv$" за полином от логарифма.
# Дано взвешенное дерево. Уметь отвечать на запросы "сумма ребер на пути из $u$ в $v$" и "изменить весь ребра $uv$" за $O(\log n)$.
# Дан массив $a$. Посчитать массив $RMQ[i][j] = min(a[i] ... a[j])$ за $O(n^2)$.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
# Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "добавить новый лист с родителем u", предподготовка $O(n \log n)$, запрос $O(\log n)$.
# Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "перевесить вершину u от ее текущего родителя к вершине v", предподготовка $O(n \log n)$, запрос $O(\log n)$.
# Докажите, что число различных как строки подстрок $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)$.
# Дано две строки $s$ и $t$. Найти их наибольшую общую подстроку за $SA + O(|s| + |t|)$.
# Обобщить алгоритм поиска наибольшей общей подстроки, если дано $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)$.
# Петя забыл про спуск по счетчику в алгоритме Укконена. Привести пример строки, на которой полученный алгоритм будет работать дольше чем за $O(n)$.
# Привести пример, когда в алгоритме Укконена в одной итерации спуск происходит по $\Omega(n)$ реберам.
# Построить суффиксный массив по суффиксному дереву за $O(n)$.
# Построить суффиксное дерево по суффиксному массиву за $O(n)$.
# Определить число различных подстрок в строке с помощью суффиксного дерева за $ST + O(n)$. ($ST$ - время построения суффиксного дерева, суффиксный массив не использовать)
# Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $ST + O(n)$
# Найти максимальную подстроку в строке, имеющую два непересекающихся вхождения за $ST + O(n)$.
# Найти строку максимальной длины, ветвящаяся влево и вправо за $ST + O(n)$.
# Найти подпалиндром максимальной длины за ST + O(n).
# Алгоритм Хьюи. Дано дерево, вершины которого раскрашенны в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы - $O(DCU)$.
# Используя результат предыдущей задачи, найти наибольшую общую подстроку $k$ строк за $O(n + DSU)$.
# Найти наибольший общий подпалиндром за $ST + O(DSU)$.
# Найти наибольший максимальный повтор за $ST + O(n)$.
# $1 | p_i = 1, d_i | \sum U_i$. Время $O(n)$.
# $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
# $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
# $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
# Обозначение prec означает, что есть ациклический граф зависимостей между работами. Пусть $f(x)$ - произвольная неубывающая функция. Обозначим как $f_{max}$ величину $\max(C_i)$. $1 | prec, p_i = 1, r_i | f_{max}$
# Обозначение pmtn означает, что работу можно прервать, а затем продолжить ее выполнение. $1 | pmtn, prec, r_i | f_{max}$
# $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
# $1 | r_i, pmtn | \sum C_i$
# $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
# $1 | r_i, p_i = 1 | \sum f_i$
# Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
# Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
# $R || Sum(C_i)$
# $P | pmtn, r_i | C_{max}$
# $Q | pmtn, r_i | C_{max}$
# $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log\log n)$
# $P | p_i = 1 | \sum w_iU_i$
# $P | p_i = 1 | \sum w_iC_i$
# $Q | pmtn | \sum C_i$
# $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
# $F | p_{ij} = 1 | \sum C_i$
# $F2 | pmtn | C_{max}$
# $F | p_{ij} = 1 | \sum U_i$
# $F | p_{ij} = 1 | \sum w_iU_i$
# $O | p_{ij} = 1 | C_{max}$
# $O | p_{ij} = 1 | \sum C_i$
# $O | p_{ij} = 1 | \sum w_iC_i$
# $O | p_{ij} = 1, d_i | -$
# $O | p_{ij} = 1 | \sum u_i$
# $O | p_{ij} = 1 | \sum w_iU_i$
# $O | p_{ij} = 1, r_i | C_{max}$
# $O2 | p_{ij} = 1, prec | \sum C_i$
</wikitex>
