Изменения
Нет описания правки
# Как найти строку длины $m$ в строке длины $n$ с использованием z-функции и O(m) дополнительной памяти?
# Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
# Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
# Докажите, что в конечном автомате для поиска подстроки в строке длины $n$ лишь $O(n)$ ребер ведут не в начальное состояние. Как это помогает сэкономить память?
# Алгоритм Саймона. Используя результат предыдущего задания, предложите алгоритм построения автомата за $O(n)$ (без множителя, зависящего от размера алфавита).
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку. Время работы должно быть полиномом от длины $s$, и $L$.
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку (по заданному модулю). Время работы должно быть полиномом от длины $s$, и $\log L$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ вхождений $s$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ непересекающихся вхождений $s$.
</wikitex>
