Поиск самого длинного палиндрома в строке

PHP Средний strings

Задача «Поиск самого длинного палиндрома в строке»

Напишите функцию, которая принимает строку и находит самую длинную подстроку-палиндром. Если таких несколько, верните первую по порядку. Строка состоит только из строчных латинских букв. Длина строки от 1 до 1000 символов. Реализуйте алгоритм с временной сложностью O(n^2) или лучше.

Формат ввода

Одна строка, содержащая произвольную последовательность строчных латинских букв.

Формат вывода

Одна строка — самая длинная подстрока-палиндром. Если палиндромов нет, выведите пустую строку.

Примеры

Пример 1

ВВОД

babad

ВЫВОД

bab

Пример 2

ВВОД

abbae

ВЫВОД

abba

Пример 3

ВВОД

a

ВЫВОД

a

main.php