ABB (Editorial)

A minimal number of characters must be added to the given string to turn it into a palindrome.

To do this, we need to find the longest palindromic suffix of the string, then take the prefix before the start of that palindrome, reverse it, and append it to the original string.

For example, the longest palindromic suffix of the string abcxqx is $xqx$. The prefix before it is $abc$. We reverse it (getting $cba$) and append it to the original string.

Consider the string rs = reverse(s) + s. Compute the $z$-function for this string.

Next, find the smallest index $i$ (such that i \ge n) for which the equality i + z_i = 2n holds. Among such indices, the value z_i will be maximal. The minimum number of characters that need to be appended to the original string to form a palindrome is n - z_i.

For the string "$abcxqx$" (length n = 6), the required index is i = 9, since 9 + z_9 = 9 + 3 = 12 = 2 * 6.

Example

Let’s consider the first example. Compute the $z$-function for the string reverse(s) + s = "bba" + "abb" = "bbaabb".

The smallest index i~(i ≥ n) for which the equality i + z_i = 2n holds is i = 4. Indeed: 4 + z_4 = 4 + 2 = 6 = 2 * 3. Therefore, the answer is n - z_i = 3 - 2 = 1. That is, it is enough to add a single character '$a$' to the string "$abb$" to obtain the palindrome "$abba$".

Algorithm implementation

The function z constructs and returns the $z$-function for the string $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;
}

The main part of the program. Read the input string $s$.

cin >> n;
cin >> s;

Construct the string rs = reverse(s) + s.

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

Compute the $z$-function for the string $rs$.

z = zfun(rs);

Find the smallest index i~(i \ge n) for which the equality i + z_i = 2n holds. Among all such indices, the value of z_i will be the largest.

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

Print the answer.

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