Всем доброго времени суток!

Изучая столь часто применяемые к строкам 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;

Обратный же переход в префикс-функцию является технически более сложной процедурой, однако, мной был найден алгоритм и для него. Переход осуществляется в три фазы:

1. Базовое восстановление. В то время как из z-функции мы могли целиком восстановить префикс-функцию, здесь нам прийдётся постараться. Для начала можно заметить, что одно и та же самая префикс-функция может быть получена из ряда z-функций. Восстановление будет возможно лишь по той причине, что лишь одна из них может быть составлена из реальной строки. Её нам и прийдётся восстановить. Для начала найдём её общий вид. Для каждой позиции, где P[i] не равна нулю, мы можем заявлять, что Z[i - P[i] + 1] не меньше, чем P[i]. Пройдёмся один раз по массиву и восстановим эти значения, которые к концу дадут нам точечные ответы в конкретных позициях Z-функции.

2. Задание базы. Теперь мы имеем общий вид z-функции. Можно проверить, что с помощью префикс-функции мы ничего лучшего не добьёмся, т.к. из общего вида получим такую же префикс-функцию, как и из корректного типа. Но нам как-то нужно восстанавливать ответ. Заметим, что если значение Z[1] у нас не равно нулю, то мы можем с уверенность утверждать, что Z[2] = Z[1] - 1, Z[3] = Z[2] - 1 и так далее, пока мы не получим 0. Итак, восстановим эту "базовую" последовательность.

3. Окончательное восстановление. Наиболее сложный этап. Просматриваем значения 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-функция) и при необходимости таким образом переходить от одной к другой. Надеюсь, что был интересен/полезен кому-нибудь и за сим откланиваюсь :)