Задача C. Частые подстроки

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В данной строке длиной N символов требуется найти подстроку длиной K символов, встречающуюся наибольшее число раз.

Например, в строке "ABC ABDC ABCC A" наиболее часто встречающаяся подстрока из двух символов — "AB", а наиболее часто встречающаяся подстрока из трёх символов — "C A".

В случае, если несколько подстрок встречаются с одинаковой частотой, следует вывести первую в лексикографическом порядке.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Первая строка входного файла содержит строку, вторая — число K.

Формат выходного файла

Выходной файл должен содержать искомую подстроку.

Ограничения

1 ≤ K ≤ N ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
sample text
1
e
2
AABBBBAA
2
BB
3
sample
6
sample

0.042s 0.007s 15