说明

给定一个字符串 s，请找出其中最长的一个回文子串。回文是指正读和反读都相同的字符串。

输入格式

• 输入只有一行，包含一个字符串 s（长度不超过100000） • 字符串 s 仅由数字和英文字母组成

输出格式

• 输出只有一行（这意味着末尾有一个回车符号），包含找到的最长回文子串 • 如果有多个相同长度的最长回文子串，输出靠前的第一个就行

样例

babad

bab

cbbd

bb

提示

1. 子串是原字符串中连续的字符序列
2. 回文子串的长度可能为1（单个字符总是回文）
3. 字符串中可能包含多个相同长度的回文子串

数据范围

• 对于100%的数据，保证 1 ≤ s.length ≤ 100000 • 字符串仅包含大小写字母和数字 • （注意双指针和动态规划方法拿50分就达标）

时间限制

1.0秒（C/C++）