Всем доброго времени суток!
Изучая столь часто применяемые к строкам Z- и префикс-функции, я задумался, а можно ли быстро (за О(n) ) переходить от одной к другой? По крайней мере, на e-maxx этого не было описано и я решил провести такой мини-анализ самостоятельно. Для начала небольшое отступление. Вспомним определения обеих функций. Итак:
Z-функцией строки s длиной n называют массив длиной n, i-ый элемент которого равен длине наибольшего общего префиксу самой строки s и её i-того суффикса, то есть, подстроки s[i..n) в 0-индексации.
Префикс-функцией строки s называют массив, i-ый элемент которого равен наибольшей длине наибольшего собственного суффикса подстроки s[0..i], совпадающего с её префиксом.
Что ж, теперь вернёмся к основной части. Мои ожидания оправдались и такие способы перехода есть. Для начала рассмотрим переход Z-func->prefix-func.
Пускай Z-функция уже посчитана и хранится в массиве Z[0..n). Будем идти в цикле, перебирая все номера i ячейки в массиве Z. Обратим внимание, что в силу определений как z-, так и префикс-функций, если элемент Z[i] не равен единице, то для всех элементов с индексом i + j, где 0 < j < Z[i] значение P[i + j] будет не меньше, чем j + 1. Несложно заметить и то, что это значение будет больше тогда и только тогда, если оно уже было установлено как более высокое когда мы исследовали меньший индекс i. Отсюда получаем алгоритм перехода от Z-функции к prefix- функции. Перебираем в цикле индекс элемента в z-функции i. Если Z[i] не равно нулю, то устанавливаем значение P[i + Z[i] - 1] равным Z[i]. После этого в цикле перебираем все номера элементов сверху вниз от i + Z[i] - 1 до i, но преждевременно прерываем наш проход, если значение P в этой точке уже подсчитано (это и обеспечивает нам линейную скорость работы, т.к. на таких условиях каждая ячейка P[i] будет просмотрено не более двух раз). Реализация перехода на С++:
for(int i = 1; i < n; i++)
if(Z[i])
for(int j = Z[i] - 1; j >= 0 && !(P[i + j]); j--)
P[i + j] = j + 1;
Обратный же переход в префикс-функцию является технически более сложной процедурой, однако, мной был найден алгоритм и для него. Переход осуществляется в три фазы:
Базовое восстановление. В то время как из z-функции мы могли целиком восстановить префикс-функцию, здесь нам прийдётся постараться. Для начала можно заметить, что одно и та же самая префикс-функция может быть получена из ряда z-функций. Восстановление будет возможно лишь по той причине, что лишь одна из них может быть составлена из реальной строки. Её нам и прийдётся восстановить. Для начала найдём её общий вид. Для каждой позиции, где P[i] не равна нулю, мы можем заявлять, что Z[i - P[i] + 1] не меньше, чем P[i]. Пройдёмся один раз по массиву и восстановим эти значения, которые к концу дадут нам точечные ответы в конкретных позициях Z-функции.
Задание базы. Теперь мы имеем общий вид z-функции. Можно проверить, что с помощью префикс-функции мы ничего лучшего не добьёмся, т.к. из общего вида получим такую же префикс-функцию, как и из корректного типа. Но нам как-то нужно восстанавливать ответ. Заметим, что если значение Z[1] у нас не равно нулю, то мы можем с уверенность утверждать, что Z[2] = Z[1] - 1, Z[3] = Z[2] - 1 и так далее, пока мы не получим 0. Итак, восстановим эту "базовую" последовательность.
Окончательное восстановление. Наиболее сложный этап. Просматриваем значения Z-функции, которые были нами восстановлены в первом этапе ДО восстановления базовой последовательности. По определению Z-функции, если в i-ой ячейке она не равна нулю, то символы в этой ячейке и в следующих Z[i] - 1 совпадают с первыми Z[i] ячейками строки. На основе этого мы можем задать им значения, соответствующие значениям в этих самых первых Z[i] ячейках. При этом нужно быть предельно аккуратным, чтобы не заполнить повторно другие ячейки, востановленные из первого этапа. Кроме того, понятно, что при задании Z[j] нам нельзя дать его больше, чем допустимо Z[i], поэтому мы выбираем минимум из Z[i] - j и Z[j]. К сожалению, мне весьма сложно словами описать, что именно делает эта часть, но код должен помочь понять это яснее... Итак, вот он:
for(int i = 1; i < n; i++) // 1 этап.
if(P[i])
Z[i - P[i] + 1] = P[i];
Z[0] = n;
if(Z[1]) // 2 этап.
for(int i = 1; i < Z[1]; i++)
Z[i + 1] = Z[1] - i;
int t;
for(int i = Z[1] + 1; i < n - 1; i++) // 3 этап.
{
t = i;
if(Z[i] && !Z[i + 1])
for(int j = 1; j < Z[i] && Z[i + j] <= Z[j]; j++)
{
Z[i + j] = min(Z[j], Z[i] - j);
t = i + j;
}
i = t;
}
P.S. хотя я и проверял такой переход на достаточно большом объёме тестов (при проверке этой задачи), я всё же мог допустить какую-то ошибку. Если это всё-таки произошло и вы её заметили, большая просьба сообщить об этом.
А пока подведём итоги. Итак, что же это даёт? Кроме того, что это просто интересный факт, некоторые лентяи, которым лень запомнить целых два способа построения этих функций (такие как я :D ), могут запомнить хотя бы одну из них (судя по всему, в данном плане выгоднее z-функция) и при необходимости таким образом переходить от одной к другой. Надеюсь, что был интересен/полезен кому-нибудь и за сим откланиваюсь :)
I think this is more simple:- this comment