Dada una cadena s, el objetivo es enteponer el menor número posible de caracteres para que el resultado sea un palíndromo. La clave está en hallar el prefijo palindrómico más largo de s: si ese prefijo tiene longitud L, basta con tomar el resto s[L…n-1], invertirlo y colocarlo al principio.

Solución con la función prefijo (estilo KMP)

Sea rev la cadena s invertida. Al construir s + "#" + rev y aplicar la función prefijo pi, el último valor de pi coincide con la longitud del prefijo palindrómico más largo de s. A partir de ese valor se obtiene el fragmento que hay que anteponer.

#include <bits/stdc++.h>
using namespace std;

class SolucionKMP {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;

        string rev = s;
        reverse(rev.begin(), rev.end());

        string combinada = s + "#" + rev;
        vector<int> pi(combinada.size(), 0);

        for (int i = 1; i < (int)combinada.size(); ++i) {
            int j = pi[i - 1];
            while (j > 0 && combinada[i] != combinada[j]) {
                j = pi[j - 1];
            }
            if (combinada[i] == combinada[j]) ++j;
            pi[i] = j;
        }

        string faltante = s.substr(pi.back());
        reverse(faltante.begin(), faltante.end());
        return faltante + s;
    }
};
</int>

Solución con Manacher

Otra alternativa consiste en isnertar un separador entre cada par de caracteres y calcular los radios de los palíndromos. Cuando un palíndromo alcanza el extremo izquierdo de la cadena transformada, su centro indica la longitud de un prefijo palindrómico de s.

class SolucionManacher {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) return s;

        string t(2 * n + 1, '#');
        for (int i = 0; i < n; ++i) t[2 * i + 1] = s[i];

        vector<int> radio(2 * n + 1, 0);
        int centro = 0, derecha = 0;
        int prefijoPal = 1;

        for (int i = 1; i < (int)t.size(); ++i) {
            int simetrico = 2 * centro - i;
            if (i < derecha) {
                radio[i] = min(derecha - i, radio[simetrico]);
            }

            int l = i - radio[i] - 1;
            int r = i + radio[i] + 1;
            while (l >= 0 && r < (int)t.size() && t[l] == t[r]) {
                --l; ++r;
            }
            radio[i] = r - i - 1;

            if (i + radio[i] > derecha) {
                centro = i;
                derecha = i + radio[i];
            }

            if (i - radio[i] == 0) {
                prefijoPal = max(prefijoPal, i);
            }
        }

        string faltante = s.substr(prefijoPal);
        reverse(faltante.begin(), faltante.end());
        return faltante + s;
    }
};
</int>