← 返回题目列表

Codeforces · 557/E

E. 安和半回文

中文机器翻译题面 查看原题

明天安将参加最难的编程考试,她应该获得优异的成绩。

在最后一节理论课上,老师介绍了半回文的概念。

字符串 t 是半回文,如果对于所有奇数位置 i ($$1 \leq i \leq \frac{|t|+1}{2}$$) 满足以下条件: ti = t|t| - i + 1,其中|t|是字符串 t 的长度(如果位置从 1 开始索引)。例如,字符串“abaa”、“a”、“bb”、“abbbaa”是半回文,而字符串“ab”、“bba”和“aaabaa”则不是。

Ann 知道在考试中她将得到字符串 s,仅由字母 a 和 b 以及数字 k 组成。为了获得优异的成绩,她必须在 s 的所有半回文子串中找到字典顺序字符串中的第 k 个。请注意,按此顺序的每个子字符串都会被视为在 s 中出现的次数。

老师保证给定的数字 k 不超过给定字符串中半回文子串的数量。

你能解决这个问题吗?

输入

输入的第一行包含字符串 s (1 ≤ |s| ≤ 5000),仅由字符 'a' 和 'b' 组成,其中 |s|是字符串 s 的长度。

第二行包含一个正整数 k——给定字符串 s 的所有半回文子串中请求字符串的字典序号。字符串从 1 开始编号。

保证数字 k 不超过给定字符串中半回文子串的数量。

输出

打印给定字符串的一个子字符串,该子字符串是给定字符串的所有半回文子字符串的字典顺序中的第 k 个子字符串。

示例

输入 #1

abbabaab
7

输出 #1

abaa

输入 #2

aaaaa
10

输出 #2

aaa

输入 #3

bbaabb
13

输出 #3

bbaabb

注意

根据定义,如果 a 是 b 的前缀且与 b 不一致,或者存在这样的 i,即 a1 = b1, a2 = b2, ... ai - 1 = bi - 1, ai < bi,则字符串 a = a1a2... an 按字典顺序小于字符串 b = b1b2... bm。

在第一个示例中,半回文子字符串是以下字符串 - a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab(列表按字典顺序给出)。