ABB#9759

ABB (Editoriale)

Alla stringa data è necessario aggiungere il numero minimo di caratteri affinché diventi un palindromo. Per fare ciò occorre trovare il palindromo più grande tra tutti i suoi suffissi, quindi prendere il prefisso fino all'inizio di tale palindromo, invertirlo e aggiungerlo alla stringa originale.

Ad esempio, il più grande suffisso palindromo della stringa $ab c x q x$ è $x q x$ . Il prefisso che lo precede è $ab c$ , lo invertiamo (otteniamo $c ba$ ) e lo aggiungiamo alla stringa originale.

Consideriamo la stringa $r s = r e v er se (s) + s$ rs = reverse(s) + s. Calcoliamo per essa la funzione $z$ .

Troviamo il minimo indice $i$ (tale che $i \geq n$ i \ge n), per cui vale l'uguaglianza $i + z_{i} = 2 n$ i + z_i = 2n. In questo caso il valore $z_{i}$ z_i sarà massimo tra tali indici. Il numero minimo di caratteri che è necessario aggiungere alla stringa originale per ottenere un palindromo è pari a $n - z_{i}$ n - z_i.

Per la stringa " $ab c x q x$ " (lunghezza $n = 6$ n = 6) l'indice necessario è $i = 9$ i = 9, poiché $9 + z_{9} = 9 + 3 = 12 = 2 * 6$ 9 + z_9 = 9 + 3 = 12 = 2 * 6.

Esempio

Consideriamo il primo esempio. Calcoliamo la funzione $z$ per la stringa $r e v er se (s) + s = " bba " + " abb " = " bbaabb "$ reverse(s) + s = "bba" + "abb" = "bbaabb".

Il minimo indice $i (i \geq n)$ i~(i ≥ n), per cui vale l'uguaglianza $i + z_{i} = 2 n$ i + z_i = 2n, è $i = 4$ i = 4. Infatti: $4 + z_{4} = 4 + 2 = 6 = 2 * 3$ 4 + z_4 = 4 + 2 = 6 = 2 * 3. Allora la risposta è pari a $n - z_{i} = 3 - 2 = 1$ n - z_i = 3 - 2 = 1. Cioè, alla stringa " $abb$ " è sufficiente aggiungere un carattere ' $a$ ' per ottenere il palindromo " $abba$ ".

Implementazione dell'algoritmo

La funzione z costruisce e restituisce la funzione $z$ per la stringa $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++

Parte principale del programma. Leggiamo la stringa di input $s$ .

cin >> n;
cin >> s;

Costruiamo la stringa $r s = r e v er se (s) + s$ rs = reverse(s) + s.

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

Calcoliamo la funzione $z$ della stringa $r s$ .

z = zfun(rs);

Troviamo il minimo indice $i (i \geq n)$ i~(i \ge n), per cui vale l'uguaglianza $i + z_{i} = 2 n$ i + z_i = 2n. Tra tutti questi indici il valore $z_{i}$ z_i sarà il più grande.

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

Stampiamo la risposta.

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