ABB#9759

ABB (Həll təhlili)

Verilmiş sətrə, palindrom olması üçün minimum sayda simvol əlavə etmək lazımdır. Bunun üçün onun bütün sonluqları (suffiksləri) arasında ən böyük palindromu tapmaq, sonra bu palindromun başlanğıcına qədər olan prefiksi götürüb, onu tərs çevirmək və ilkin sətrə əlavə etmək lazımdır.

Məsələn, $ab c x q x$ sətrinin ən böyük palindromik sonluğu $x q x$ -dir. Ona qədər olan prefiks — $ab c$ -dir, onu tərs çeviririk (nəticədə $c ba$ alınır) və ilkin sətrə əlavə edirik.

$r s = r e v er se (s) + s$ rs = reverse(s) + s sətrinə baxaq. Onun üçün $z$ -funksiyasını hesablayaq.

$i + z_{i} = 2 n$ i + z_i = 2n bərabərliyi ödənən ən kiçik $i$ indeksini (elə ki, $i \geq n$ i \ge n) tapaq. Bu zaman belə indekslər arasında $z_{i}$ z_i qiyməti maksimal olacaq. İlkin sətri palindroma çevirmək üçün ona əlavə edilməli olan minimum simvol sayı $n - z_{i}$ n - z_i-yə bərabərdir.

" $ab c x q x$ " sətri üçün (uzunluq $n = 6$ n = 6) axtarılan indeks $i = 9$ i = 9-dur, çünki $9 + z_{9} = 9 + 3 = 12 = 2 * 6$ 9 + z_9 = 9 + 3 = 12 = 2 * 6.

Nümunə

Birinci nümunəyə baxaq. $r e v er se (s) + s = " bba " + " abb " = " bbaabb "$ reverse(s) + s = "bba" + "abb" = "bbaabb" sətri üçün $z$ -funksiyasını hesablayaq.

$i + z_{i} = 2 n$ i + z_i = 2n bərabərliyi ödənən ən kiçik $i (i \geq n)$ i~(i ≥ n) indeksi $i = 4$ i = 4-dür. Doğrudan da: $4 + z_{4} = 4 + 2 = 6 = 2 * 3$ 4 + z_4 = 4 + 2 = 6 = 2 * 3. Onda cavab $n - z_{i} = 3 - 2 = 1$ n - z_i = 3 - 2 = 1-ə bərabərdir. Yəni, " $abb$ " sətrinə palindrom " $abba$ " almaq üçün cəmi bir ' $a$ ' simvolu əlavə etmək kifayətdir.

Alqoritmin realizasiyası

z funksiyası $s$ sətri üçün $z$ -funksiyasını qurur və qaytarır.

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++

Proqramın əsas hissəsi. Giriş sətri $s$ -i oxuyuruq.

cin >> n;
cin >> s;

$r s = r e v er se (s) + s$ rs = reverse(s) + s sətrini qururuq.

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

$r s$ sətrinin $z$ -funksiyasını hesablayırıq.

z = zfun(rs);

$i + z_{i} = 2 n$ i + z_i = 2n bərabərliyi ödənən ən kiçik $i (i \geq n)$ i~(i \ge n) indeksini tapırıq. Bütün belə indekslər arasında $z_{i}$ z_i qiyməti ən böyük olacaq.

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

Cavabı çıxarırıq.

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