查找字符串中最长的回文子串

PHP Medium strings

任务 «查找字符串中最长的回文子串»

写一个函数，它接收一个字符串并找出最长的回文子串。如果有多个，则返回按顺序出现的第一个。字符串仅由小写拉丁字母组成。字符串长度在1到1000个字符之间。实现一个时间复杂度为O(n²)或更优的算法。

输入格式

一行字符串，包含任意的小写拉丁字母序列。

输出格式

一行 — 最长的回文子串。如果没有回文，则输出空字符串。

示例

示例 1

输入

babad

输出

bab

示例 2

输入

abbae

输出

abba

示例 3

输入

a

输出

a

main.php