Форум VGA Planets

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-тестами. Сопроводительное письмо должно содержать основную идею
решения.

valexey

The Q

Откуда: Москва, Россия

Здесь с 30.11.2006

Сообщений: 1,275

Re: Задачка

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

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

---

cat /dev/zero > /dev/null

valexey

The Q

Откуда: Москва, Россия

Здесь с 30.11.2006

Сообщений: 1,275

Re: Задачка

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

---

cat /dev/zero > /dev/null