9759. ABB

Фернандо был нанят Университетом Ватерлоо для завершения проекта развития, который университет начал совсем недавно. За пределами кампуса университет хотел построить представительскую улицу бунгало для важных иностранных посетителей и сотрудников.

В настоящее время улица застроена лишь частично, она начинается на берегу озера и продолжается к лесу, где и заканчивается. Задача Фернандо - закончить улицу в конце леса, построив там некоторое количество бунгало. Все существующие бунгало стоят на одной стороне улицы, а новые должны быть построены на той же стороне. Бунгало бывают разных типов и окрашены в разные цвета.

Вся улица кажется Фернандо немного хаотичной. Он боится, что это будет выглядеть еще более хаотично, когда он добавит новые бунгало собственного дизайна. Чтобы уравновесить хаос всех форм бунгало, он хочет внести некоторый порядок в их расположение, выбрав подходящие цвета для новых бунгало. Когда проект будет завершен, вся последовательность цветов бунгало будет симметричной, то есть последовательность цветов будет одинаковой при наблюдении с любого конца улицы.

Среди других вопросов Фернандо задается вопросом, какое минимальное количество новых бунгало ему необходимо построить и покрасить надлежащим образом, чтобы завершить проект, соблюдая при этом установленные им самим ограничения на цвета бунгало.

Вход. В первой строке находится одно целое число n (1 ≤ n ≤ 4 * 10⁵) – количество существующих бунгало на улице. В следующей строке описывается последовательность цветов существующих бунгало, начиная с начало улицы у озера. Строка содержит одну строку, состоящую из n строчных букв (от “a” до “z”), где разные буквы представляют разные цвета.

Выход. Выведите минимальное количество бунгало, которое нужно добавить в конец улицы и соответствующим образом покрасить, чтобы удовлетворить требования Фернандо по симметрии цвета.

Пример входа 1	Пример выхода 1
3 abb	1

Пример входа 2	Пример выхода 2
12 recakjenecep	11

РЕШЕНИЕ

z-функции

Анализ алгоритма

К строке следует добавить минимальное количество букв так, чтобы она стала палиндромом. Фактически следует среди всех суффиксов строки найти палиндром наибольшей длины, после чего взять префикс до этого палиндрома, развернуть его и приписать к исходной строке.

Например, наибольшим палиндромом – суффиксом для строки abcxqx является xqx. Переворачиваем префикс: cba, и приписываем его к исходной строке.

Рассмотрим строку rs = reverse(s) + s. Вычислим для нее z-функцию.

Найдем наименьший индекс i (i ≥ n), для которого i + z[i] = 2n. Для такого индекса i значение z[i] будет наибольшим. Количество символов, которое следует дописать к исходной строке чтобы сделать ее палиндромом, равно n – z[i].

Для приведенного примера таковым индексом будет i = 9, так как 9 + z[9] = 9 + 3 = 12 = 2 * 6, где 6 – длина строки “abcxqx”.

Пример

Рассмотрим первый пример. Вычислим z-функцию для строки reverse(s) + s = “bba” + “abb” = “bbaabb”.

Наименьшим индексом i (i ≥ n), для которого i + z[i] = 2n, будет = 4. Действительно, 4 + z[4] = 4 + 2 = 6 = 2 * 3. Ответом будет значение n – z[i] = 3 – 2 = 1. Действительно, к строке “abb” достаточно добавить один символ ‘a’, чтобы получить палиндром “abba”.

Реализация алгоритма

Функция z строит и возвращает z-функцию для строки s.

vector<int> zfun(string s)

{

int i, l, r, len = s.size();

vector<int> z(len, 0);

l = r = 0;

for (i = 1; i < len; i++)

{

if (i <= r) z[i] = min(r - i + 1, z[i - l]);

while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;

if (i + z[i] - 1 > r)

{

l = i;

r = i + z[i] - 1;

}

}

return z;

}

Основная часть программы. Читаем входную строку s.

cin >> n;

cin >> s;

Строим строку rs = reverse(s) + s.

rs = s;

reverse(rs.begin(), rs.end());

rs += s;

Вычисляем z-функцию строки rs.

z = zfun(rs);

Находим наименьший индекс i (i ≥ n), для которого i + z[i] = 2n. Для такого индекса i значение z[i] будет наибольшим.

for (i = n; i < rs.size(); i++)

if (i + z[i] == 2 * n)

{

Выводим ответ.

cout << n - z[i] << endl;

break;

}