对于一个字符串 $s$，求出一个尽可能短的回文字符串 $s^{*}$，同时使得 $s$ 是 $s^{*}$ 的前缀。
$|s|\leq 10^5$.