Busca el palíndromo más largo en una cadena

PHP Medium strings

Tarea «Busca el palíndromo más largo en una cadena»

Escribe una función que tome una cadena y encuentre la subcadena palindrómica más larga. Si hay varias, devuelve la primera en orden. La cadena consiste solo en letras latinas minúsculas. La longitud de la cadena es de 1 a 1000 caracteres. Implementa un algoritmo con una complejidad temporal de O(n^2) o mejor.

Formato de entrada

Una línea que contiene una secuencia arbitraria de letras latinas minúsculas.

Formato de salida

Una línea: la subcadena palindrómica más larga. Si no hay palíndromos, imprime una cadena vacía.

Ejemplos

Ejemplo 1

ENTRADA

babad

SALIDA

bab

Ejemplo 2

ENTRADA

abbae

SALIDA

abba

Ejemplo 3

ENTRADA

a

SALIDA

a

main.php