ABB#9759

ABB (Розбір)

До заданого рядка потрібно додати мінімальну кількість символів, щоб він став паліндромом. Для цього потрібно знайти найбільший паліндром серед усіх його суфіксів, потім взяти префікс до початку цього паліндрома, розвернути його і приписати до вихідного рядка.

Наприклад, найбільшим паліндромним суфіксом рядка $ab c x q x$ є $x q x$ . Префікс до нього — $ab c$ , розвертаємо його (отримуємо $c ba$ ) і приписуємо до вихідного рядка.

Розглянемо рядок $r s = r e v er se (s) + s$ rs = reverse(s) + s. Обчислимо для нього $z$ -функцію.

Знайдемо найменший індекс $i$ (такий, що $i \geq n$ i \ge n), для якого виконується рівність $i + z_{i} = 2 n$ i + z_i = 2n. При цьому значення $z_{i}$ z_i буде максимальним серед таких індексів. Мінімальна кількість символів, яку необхідно дописати до вихідного рядка, щоб отримати паліндром, дорівнює $n - z_{i}$ n - z_i.

Для рядка " $ab c x q x$ " (довжина $n = 6$ n = 6) потрібний індекс $i = 9$ i = 9, оскільки $9 + z_{9} = 9 + 3 = 12 = 2 * 6$ 9 + z_9 = 9 + 3 = 12 = 2 * 6.

Приклад

Розглянемо перший приклад. Обчислимо $z$ -функцію для рядка $r e v er se (s) + s = " bba " + " abb " = " bbaabb "$ reverse(s) + s = "bba" + "abb" = "bbaabb".

Найменшим індексом $i (i \geq n)$ i~(i ≥ n), для якого виконується рівність $i + z_{i} = 2 n$ i + z_i = 2n, є $i = 4$ i = 4. Дійсно: $4 + z_{4} = 4 + 2 = 6 = 2 * 3$ 4 + z_4 = 4 + 2 = 6 = 2 * 3. Тоді відповідь дорівнює $n - z_{i} = 3 - 2 = 1$ 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;
}

C++

Основна частина програми. Читаємо вхідний рядок $s$ .

cin >> n;
cin >> s;

Будуємо рядок $r s = r e v er se (s) + s$ rs = reverse(s) + s.

rs = s;
reverse(rs.begin(), rs.end());
rs += s;

Обчислюємо $z$ -функцію рядка $r s$ .

z = zfun(rs);

Знаходимо найменший індекс $i (i \geq n)$ i~(i \ge n), для якого виконується рівність $i + z_{i} = 2 n$ i + z_i = 2n. Серед усіх таких індексів значення $z_{i}$ z_i буде найбільшим.

for (i = n; i < rs.size(); i++)
  if (i + z[i] == 2 * n)
  {

Виводимо відповідь.

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