1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Строка $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>
