输出最长回文子串

给定一个长度为 N 的字符串 s，找到 s 中的最长回文子串(Longest Palindromic Substring，简称：LPS)。

输入格式

字符串 s。

输出格式

输出给定字符串中最长的回文子串。（如果存在多个长度相等的最长回文子串，输出第1个）

baacaaba

baacaab

提示

1≤N≤10000

时间限制: 1000ms

内存限制: 512MB