🐰😺🔍 兔猫信奥学院·加菲老师的回文探秘之旅 🔍😺🐰

信奥学院的藏书阁里，珍藏着一部世代相传的古籍——《镜中谜语》。加菲老师拿出其中一页，对小兔和小猫说道：“在这行文字里，总有一些最动人的回文——从前往后和从后往前读都一样。请你们帮忙找出给定字符串中最长的这段回文子串，让古籍的秘密重见天日！”

输入格式

输入仅包含一行，由数字和英文字母组成的字符串 s。

• $1 \le |s| \le 10000$

输出格式

输出一个字符串，表示 s 中最长的回文子串。

如果有多种答案，输出任意一种均可。

样例 1

babad

bab

• 解释：
  “bab” 和 “aba” 均为长度 3 的回文子串，任意输出其一。

样例 2

cbbd

bb

• 解释：
  最长回文子串为 “bb”。

🎓 加菲老师寄语：
Manacher 算法能在 $O(n)$ 时间内找到最长回文子串，是字符串算法中的皇冠利器。掌握它，你将在更大规模文本处理和生物序列分析中大放异彩！