Задача L. Сжатый префиксный словарь

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

Условие

Пусть имеется текстовая строка S, состоящая из цифр и букв латинского алфавита. При этом полагается, что регистр их написания неважен, т.е. заглавные и строчные символы эквивалентны между собой. На основе указанной строки требуется сформировать словарь T, в котором отдельным ее подстрокам ставятся в соответствие некоторые числовые коды. Описание вычислительной процедуры для получения таких кодов приводится ниже:

  1. на начальном этапе алгоритма создадим пустой словарь T и заведем счетчик k = 0;
  2. будем двигаться по заданной строке, читая ее символы слева направо;
  3. находясь в начале очередного суффикса строки S, выберем наименьший непустой его префикс, который отсутствует в словаре T;
  4. выбранный на предыдущем этапе префикс добавим в словарь, указав в качестве числового кода его порядковый номер k;
  5. увеличим счетчик k на единицу;
  6. дальнейший поиск продолжается с позиции, следующей после указанного префикса.

Если при попытке добавления очередной подстроки число записей в словаре превысит некоторое заданное n, словарь должен быть очищен. Счетчик k при этом обнуляется. Последний считанный символ (в окончании текущего префикса) возвращается в поток, и процедура возобновляется с той же позиции, в которой она остановилась.

В качестве ответа требуется вывести содержимое такого словаря на момент окончания входной строки.

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

В первой строке входного файла "input.txt" записано натуральное число n.
Далее следует строка S, для которой необходимо построить словарь.

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

В выходной файл "output.txt" нужно вывести все содержащиеся в словаре подстроки, приведенные к одному регистру и расположенные в лексикографическом порядке.
Напротив каждой такой строки (через пробел) следует указать ее порядковый номер.

Ограничения

10 ≤ n ≤ 5000, 0 < |S| ≤ 2 ⋅ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
50
BaNaNAbaNAnaBaNaNAba
a 1
ab 4
aba 9
an 3
ana 5
b 0
ba 7
n 2
na 6
nan 8
2
10
12uitNp3zxrv45swe6qa
4 2
5 3
6 7
a 9
e 6
q 8
r 0
s 4
v 1
w 5

0.103s 0.020s 15