Encontrar o palíndromo mais longo em uma string

PHP Medium strings

Tarefa «Encontrar o palíndromo mais longo em uma string»

Escreva uma função que recebe uma string e encontra a substring palíndroma mais longa. Se houver várias, retorne a primeira em ordem. A string consiste apenas em letras minúsculas do alfabeto latino. O comprimento da string é de 1 a 1000 caracteres. Implemente um algoritmo com complexidade de tempo O(n^2) ou melhor.

Formato de Entrada

Uma string contendo uma sequência arbitrária de letras minúsculas do alfabeto latino.

Formato de Saída

Uma string — a substring palíndroma mais longa. Se não houver palíndromos, imprima uma string vazia.

Exemplos

Exemplo 1

ENTRADA

babad

SAÍDA

bab

Exemplo 2

ENTRADA

abbae

SAÍDA

abba

Exemplo 3

ENTRADA

a

SAÍDA

a

main.php