Привет всем! Помогите с задачкой.
Необходимо реализовать функцию подбора наиболее часто встречающихся запросов по частично введенной строке.

Есть файл с входными значениями формата (строка пробел число), кол-во таких значений не более 10 ⁵
в этом же файле есть набор подстрок в формате (строка), таких значений не более 15000

Необходимо для каждой подстроки вывести в выходной файл 10 наиболее часто встречающихся строк (запросов из первой части файла).

Алгоритм следующий:
читаю все строки и числа в TreeMap<String, Integer> map
читаю все подстроки в ArrayList<String> list

Для каждой подстроки нахожу совпадения map.subMap()
Полученный Map сортирую по значению и пишу в файл 10 самых часто встречающихся запросов

Собственно говоря все работает... НО временные ограничения 2 сек, а у меня 8-12 сек. и узкое место именно эта сортировка.
Вопрос вот в чем:
Может быть я принципиально что-то не так делаю?
Можно ли ускорить сортировку (писать их в отдельные потоки/нити, или делать частичную сортировку, правда не знаю пока как)?

Файл с кодом во вложении.
Заранее спасибо за любые ответы.

Пример входного файла:
6
base 10
bass 20
back 1
ablack 7
black 7
good 3
8
b
ba
bas
a
ab
ga
go
a

где первая цифра (6) - количество запросов
далее сами запросы (уникальны) и частота встречаемости

далее цифра (8) - подстроки (не уникальны и выполняются для каждой , неважно, встречалась она или нет)
далее идут подстроки

Выходной файл должен иметь вид:
bass
base
black
back

bass
base
back

bass
base

ablack

ablack


good

ablack

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

Blazkowicz, походу да.... был там давно-давно..
спасибо за наводку.

Blazkowicz,
Все строки и не сортируются.
сначала выделяются совпадения подстроки в запросах, и уже затем полученный Map сортируется по Value для выделения наиболее часто встречаемых запросов.

mayton,

3
mayton 1
Fabus 2
Blashkovich 3
2
m
B


Могут ли быть дубликаты ключей в первой части?
Нет, в первой части значения уникальны.

Почему речь идет о "подстроке"? Для "mayton" будет ли "ton" являться подстрокой в данной имплементации алгоритма?
Идет речь именно о начале строк, т.е. подстрока - это начало строки запроса
запросы
bass 40
base 30
blackbass 10

подстрока
ba

вывод: (в порядке убывания частоты запросов)
bass 40
base 30

Всем спасибо, задачу решил, небольшая оптимизация кода помогла.
файл с кодом и генератором прикрепил, вдруг кому понадобится.
Кстати при реализация с Trie так и не получилось влезть в рамки 100 Мб. Ну да и ладно.
Еще раз всем спасибо.