Честно говоря, я не ожидал такой бурной реакции со стороны читателей. И это меня только радует. То, что я был буквально завален письмами как по электронной почте, так и в обычных конвертах, дает основание полагать, что рубрика будет развиваться и развиваться. Конечно же, с вашей помощью.

Перейдем, собственно, к задаче. Для начала, в общем, напомню ее условие. Требовалось подсчитать, сколько раз встречались строки файла IN1.TXT в строках файла IN2.TXT. Кроме того, снималось ограничение на длину строк обоих файлов.

К сожалению, надо отметить, что теорический подход к решению задачи был "не в чести". Больше всего было простых решений подсчета, иногда слегка соптимизированных. Поэтому, думаю, не лишним будет процитировать два "неподписанных" письма:

Первое письмо:

Н.Вирт, "Алгоритмы и структуры данных", М., "Мир", 1998

1.12.5 "Поиск в строке. Алгоритм Кнута, Морисса и Пратта". (стр. 76-83)

1.12.6. "Поиск в строке. Алгоритм Боуера и Мура". (стр.83-87)

Программист, не пытавшийся нажать клавишу "any key", сможет реализовать этот алгоритм, достаточно быстро разобравшись в принципах его работы, немного модифицировав для подсчета не всех вхождений, а определения числа строк.

К сожалению, не указаны критерии оценки правильно работающих алгоритмов. Что важнее: время, используемая память, величина программы (source or exe)?

О сроках. Подписчики получают в Минске газету в пятницу и открывают ее в лучшем случае после 12-13 часов. Не все имеют ПЭВМ дома, а идею необходимо не только проверить, но также реализовать и оформить. Поэтому срок до 28 июня явно недостаточен.

К проблеме сроков и условий конкурса мы вернемся в конце статьи. А сейчас почитаем следующее письмо:

Поиск первого вхождения подстроки в строку можно выполнить за время O(l+n), где n - длина строки X, l - длина подстроки Y.

Данный алгоритм можно найти:

А.Ахо, Дж.Хопкрафт, Дж.Ульман "Построение и анализ вычислительных алгоритмов", М., "Мир", 1979, стр.367-373.

Остальное - очевидно: ищем первую подстроку из файла IN1.TXT во всех строках файла IN2.TXT, 2-ую подстроку и так далее.

Пусть m - число строк в IN1.TXT, li - длина i-той строки, i=1..m, n - число строк в файле IN2.TXT, tj - длина j-той строки, j=1..n

Тогда поиск первого вхождения i-той подстроки IN1.TXT для всех строк из IN2.TXT потребует

Общее время работы алгоритма

В общем, как раз реализации этого известного алгоритма я и добивался от участников конкурса. И мои надежды, в общем-то, оправдались. Но не будем спешить.

Что меня порадовало, так это появление "нераспространенных" языков программирования. Причем два из них крепко связаны с Интернет-разработками. Поэтому я отдельно хочу отметить авторов. "Интернет-языками" пользовались Андрей Гриневич (Perl) и Анатолий Казачков (Java). Кроме них, "нераспространенным" языком Turbo Prolog воспользовался Ковальков Александр. Хочу сказать, что программы написаны достаточно хорошо, но без использования вышеописанных алгоритмов. А для Андрея Гриневича хочу добавить, что его программу на Perl можно сделать более быстрой, если предварительно провести прекомпиляцию регулярных выражений поиска. Хотя его программа была самой короткой (14 строчек), чего и можно было ожидать от этого языка программирования.

Хочется отметить работы Алексея Фролова (г.Гомель), участника под псевдонимом Ant ([email protected]) и Алексея Санько. Их программы выделяются оригинальностью своих алгоритмов на фоне остальных.

Совсем чуть-чуть от победителей отстали Руденя Виталий (г.Солигорск) и Ломоносов Сергей (г.Минск). Мы надеемся, что в дальнейшем они составят серьезную конкуренцию участникам конкурсов.

А теперь перейдем к победителям:

Третье место занял Головнёв Арсений (г.Минск). Приз - подписка на "КВ" и компакт-диск "Новый Русский Офис 97 SR2".

Второе место занял Владимир Танкович. Приз - подписка на "КВ" и компакт-диск "Microsoft Windows 98, Adobe Photoshop 5.0 и др.".

Первое место занял Сергей Вязков (г.Минск, БГУ, ФПМИ). Он смог в столь короткие сроки реализовать вышеуказанный алгоритм с требуемыми ограничениями.

Приз победителю - подписка на "КВ" на 2000 год и "Большая энциклопедия Кирилла и Мефодия" на двух CD-дисках.

Надеемся, победители свяжутся с редакцией на предмет получения призов.

А сейчас я бы хотел поговорить с вами о теме, затронутой в первом цитируемом письме. Два первых конкурса проводились без достаточно определенных критериев и правил. С одной стороны, это позволяет выделять интересные работы, с другой, достаточно сложно индивидуально оценивать каждое письмо. Тем более, нет сил ответить и выразить благодарность лично всем участникам, приславшим письма. И хотелось бы, чтобы и задачи, и решения были на более высоком уровне. Поэтому, если у вас есть идеи о проведении данных конкурсов, если вы можете помочь своими мыслями или организационно (может, есть смысл проводить вначале региональные туры), то напишите на адрес редакции на мое имя или с пометкой "Конкурсы программирования" или присылайте сообщения на мой электронный адрес.

Вадим НАРЕЙКО,
[email protected],
www.belcaf.com