CF557E Ann and Half-Palindrome

明天 Ann 将要参加一场最难的编程考试，她需要取得优异的成绩。 在最后一堂理论课上，老师介绍了“半回文串”的概念。 当且仅当字符串 $t$ 满足对于所有奇数位置 $i$ ($1 \le i \le |t|$)，有 $t_i = t_{|t|-i+1}$ 成立时，称字符串 $t$ 是一个半回文串。其中 $|t|$ 表示字符串 $t$ 的长度，且位置从 $1$ 开始计数。例如，字符串 "abaa"、"a"、"bb"、"abbbaa" 都是半回文串，而 "ab"、"bba" 和 "aaabaa" 不是。 Ann 知道在考试时，她会得到一个仅包含字母 a 和 b 的字符串 $s$，以及一个整数 $k$。为了取得优异成绩，她需要在字符串 $s$ 的所有半回文子串中，按字典序找到第 $k$ 个子串。注意，对于重复出现的子串，每次出现都需要计入排序。 老师保证，所给的数字 $k$ 不会超过字符串 $s$ 的所有半回文子串的数量。 你能解决这个问题吗？

输入的第一行为字符串 $s$（$1 \le |s| \le 5000$），仅包含字符 'a' 和 'b'，其中 $|s|$ 表示字符串 $s$ 的长度。 第二行为正整数 $k$，表示在字符串 $s$ 的所有半回文子串中字典序第 $k$ 小的子串。子串从 $1$ 开始编号。 保证 $k$ 不会超过字符串 $s$ 的所有半回文子串的数量。

输出在字符串 $s$ 的所有半回文子串中字典序第 $k$ 小的那个子串。

根据定义，字符串 $a = a_1a_2\ldots a_n$ 在字典序上小于字符串 $b = b_1b_2\ldots b_m$，如果满足以下条件之一： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 或者存在下标 $i$，使得 $a_1=b_1, a_2=b_2, \ldots, a_{i-1}=b_{i-1}$，且 $a_i < b_i$。 在第一个样例中，所有半回文子串的字典序排列如下：a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab（该列表已经按字典序给出）。 由 ChatGPT 5 翻译