Deje que la longitud de la cadena original sea N. Suponga que la solución óptima nos tiene agregando caracteres M para convertirla en un palíndromo. Entonces, los primeros M caracteres de la cadena original serían idénticos a los M caracteres agregados al revés. Además, los últimos caracteres NM de la cadena original tendrían que ser un palíndromo.
Por lo tanto, el problema es equivalente a encontrar el sufijo más largo de la cadena original que es un palíndromo. Esto se puede hacer fácilmente mediante hash. Para obtener una descripción de cómo se realiza el hash, eche un vistazo a la descripción del algoritmo Rabin-Karp en el tutorial de Topcoder. Si el hash del sufijo es igual al hash de su reverso, es un palíndromo. Dado que se puede agregar un carácter al hash en el tiempo O (1), se puede verificar la palindromidad de todos los sufijos en el tiempo O (N).
Alternativamente, puede usar el algoritmo KMP para comparar entre la cadena original y la cadena invertida. Encuentra el prefijo más largo de la cadena invertida que es idéntico a un sufijo de la cadena original. Este es el sufijo palíndromo más largo de la cadena. Este enfoque es O (N) también.
- ¿Cuáles son los algoritmos populares de aprendizaje automático en línea y sus casos de uso típicos?
- ¿Qué es un contador Loglog?
- ¿Puedes compartir tu algoritmo de encontrar la longitud del AP más largo en una matriz dada?
- ¿Es una buena idea modelar otras estructuras de datos después de STD :: Vector?
- Insertar un elemento en un montón toma O (log n). ¿Aún si insertamos n elementos en el montón, resulta ser O (n)?
