Рассмотрим следующую задачу:
Дано корневое дерево с $$$n$$$ вершинами. В каждой вершине записан символ $$$c_v \ (1 \leq c_v \leq C)$$$, где $$$C$$$ — размер алфавита. Для каждой вершины $$$v \ (1 \leq v \leq n)$$$ требуется посчитать значение префикс функции на вертикальном пути от корня до $$$v$$$.
Наивное решение
Во время поиска в глубину будем поддерживать стек со значениями префикс функции и пересчитывать ее также, как и в стандартном варианте для 1 строки.
Вспомним, что префикс функция имеет амортизированную асимптотику, поэтому можно построить тест — кисточка, где бамбук состоит из одинаковых букв, а в листьях другие символы. Для каждого листа префикс функция будет искаться за глубину дерева, поэтому итоговая асимптотика составить $$$O (n^2)$$$.
Немного умнее
Будем считать $$$dp[v][sym]$$$ — значение префикс функции в вершине $$$v$$$, если мы перешли в нее по символу $$$sym$$$. Пересчитывать такую динамику удобнее всего лениво, используя пересчет префикс функции из стандартного алгоритма, но учитывая символ по которому перешли в вершину. Всего состояний динамики $$$n \cdot C$$$, и пересчитываются они суммарно за $$$O (n \cdot C)$$$, поэтому асимптотика будет $$$O (n \cdot C)$$$.
Что-то умное
Для удобства понимания представим переходы префикс функции как переходы автомата.
Помимо обычной префикс функции будем считать значение префикс функции, которое оканчивается на отличную от текущей букву, если переходить по переходам префикс функции. Более формально — ищем ближайший префикс после которого идет другой символ. Теперь при вычислении обычной префикс функции мы можем ходить по этим переходам и получить магическую асимптотику в $$$O (n)$$$.
Доказательство данного факта является нетривиальной задачей и остается читателям в качестве упражнения со звездочкой. Предлагается написать его в комментарии.
Задачи на эту идею:
Comments (0)
