| Codeforces Round 311 (Div. 2) |
|---|
| Закончено |
Завтра Ане предстоит сдавать самый сложный экзамен по программированию, на котором ей необходимо получить отличную оценку.
На последнем теоретическом занятии преподаватель ввел понятие полупалиндрома.
Строка t является полупалиндромом, если для всех нечетных позиций i (
) выполняется условие ti = t|t| - i + 1, где |t| — длина строки t, а нумерация позиций начинается с единицы. Например, строки "abaa", "a", "bb", "abbbaa" являются полупалиндромами, а строки "ab", "bba" и "aaabaa" — нет.
Аня узнала, что на экзамене она получит строку s, состоящую только из латинских символов a и b, а также число k. Для получения отличной оценки ей необходимо будет найти k-ю в лексикографическом порядке подстроку данной строки s среди тех подстрок, которые являются полупалиндромами. При этом, каждая подстрока в этом порядке учитывается столько раз, сколько раз она встречается в s.
Преподаватель гарантирует, что данное число k не превышает количества подстрок данной строки, которые являются полупалиндромами.
А вы сможете справиться с такой задачей?
В первой строке входных данных следует строка s (1 ≤ |s| ≤ 5000), состоящая только из символов 'a' и 'b', где |s| — длина строки s.
Во второй строке следует целое положительное число k — лексикографический номер искомой подстроки-полупалиндрома среди всех подстрок-полупалиндромов заданной строки s. Нумерация этих подстрок начинается с единицы.
Гарантируется, что число k не превышает количества подстрок данной строки, которые являются полупалиндромами.
Выведите подстроку заданной строки, которая является k-й в лексикографическом порядке из тех подстрок заданной строки, которые являются полупалиндромами.
abbabaab
7
abaa
aaaaa
10
aaa
bbaabb
13
bbaabb
По определению, строка a = a1a2... an лексикографически меньше строки b = b1b2... bm, если либо a является префиксом b и не совпадает с b, либо существует такое i, что a1 = b1, a2 = b2, ... ai - 1 = bi - 1, ai < bi.
В первом примере подстроками-полупалиндромами являются следующие строки — a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab (список задан в лексикографическом порядке).
