#1 19.02.2007 15:22:47

Ingersol
Участник
Здесь с 16.01.2007
Сообщений: 46

Задачка

Дан текстовый файл, в котором 1 миллион строк. Каждая строка состоит из 3-5
символов английского алфавита (только нижний регистр). Никакой другой
информации об особенностях данных нет.

Будем говорить, что две строки s1 и s2 принадлежат одной группе, если
находится три символа, которые принадлежат одновременно s1 и s2. Таким
образом, группа однозначно идентифицируется тремя неупорядоченными
символами, которые встречаются в каждой из строк, принадлежащих этой группе.
Группа может содержать повторяющиеся символы.

Требуется написать программу, которая получает на вход описанный выше
текстовый файл, а на выходе выдает файл следующего вида:

G1 id11 id12 id13 : id1N\n

G2 id21 id22 id23 : id2M\n

:

Где Gi - это идентификатор группы, состоящий из трех символов, упорядоченных
по возрастанию, id - порядковые номера строк (нумерация с единицы), входящих
в эту группу, упорядоченные по возрастанию, разделённые пробелами. Все
строки, входящие в результирующий файл, должны быть упорядочены по
лексикографическому возрастанию группы. Пример:

afr 12 56 78

agj 3 12 45 89

bbz 14 54 70

:

На машине 3GHz, 2Gb обработка должна выполняться не более чем за 5 минут.


Решение должно состоять из java-кода и файла run.bat, который запускает
обработку и принимает 2 параметра: путь к исходному файлу и путь к
результирующему файлу. Код должен быть откомментирован и покрыт
jUnit-тестами. Сопроводительное письмо должно содержать основную идею
решения.

Вне форума

#2 21.02.2007 19:47:41

valexey
The Q
Откуда: Москва, Россия
Здесь с 30.11.2006
Сообщений: 1,274

Re: Задачка

Реализовал на сях. Левой паткой через stl. На некоторых тестах работает быстрее твоего :-)

Кстати, вышли мне поправленую версию решения плз.


cat /dev/zero > /dev/null

Вне форума

#3 21.02.2007 19:47:58

valexey
The Q
Откуда: Москва, Россия
Здесь с 30.11.2006
Сообщений: 1,274

Re: Задачка

Да, в виде бинарников конечно, не исходников.


cat /dev/zero > /dev/null

Вне форума

Подвал форума

Под управлением FluxBB
Модифицировал Visman