Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Поиск файла

Задачу добавил: alef

Успешно сдано решений: 1

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

В большинстве операционных систем имеется возможность отыскивать файл
по заданному образцу с использованием символов подстановки. Традиционно
* означает любое количество (любых) символов, ? - один (любой) символ.
Но программисты Closed Systems решили позаботиться о пользователе еще больше.
Они предположили, что пользователь может совершать опечатки (заменить 1 букву другой), и поэтому нужно
учитывать, что в образце имеется некоторое их количество (устанавливается
пользователем). Опечатки делятся на две категории: в первую попадают ситуации,
когда символ набран в другом регистре (A вместо a), во вторую - все остальные.

В результате разработанная ими система поиска не только выдает имена файлов,
в точности соответствующие образцу, но и имена, которые соответствуют
образцу с одной, двумя и т.д. (до определенного заранее количества) опечатками.
Система поиска сортирует имена по возрастанию количества опечаток,
при одинаковом количестве опечаток - сначала выводятся имена файлов
с опечатками "первой категории", затем - с опечатками "второй категории".
При прочих равных имена файлов сортируются по алфавиту.

Формат входного файла input.txt
Первая строка: целое число N (0<=N<=3) - допустимое количество опечаток,
через пробел - образец, составленный из букв латинского алфавита а также
знаков * и ? (образец не длиннее 50 символов)

Следующие строки содержат описание дерева каталогов в следующем формате.
Каждая строка содержит либо имя файла, либо описание начала каталога
(перед именем каталога стоит символ #), либо описание завершения каталога
(перед именем каталога стоят два символа #).
Последняя строка файла - это строка, содержащая описание завершения
корневого каталога (имя которого указано во второй строке)

Имена каталогов и файлов состоят из букв латинского алфавита, цифр, символов
подчеркивания и точек. Длины имен файлов и каталогов не превосходят 250 символов, всего в
описании дерева каталогов содержится не более 2000 строк

Формат выходного файла output.txt
Отсортированный, как описано в условии, список подходящих имен файлов - по одному в
строке

Пример входного файла
2 *.rtf
#folder1
#temp
document1.doc
dacumetn2.doc
doc3.rTf
doc4.RTF
roc12.RtF
wave.mp3
##temp
#public
##public
#private
techn.ftr
qwerty.swf
##private
##folder1

Пример выходного файла
doc3.rTf
roc12.RtF
qwerty.swf
techn.ftr

Сдать задачу

Задать вопрос жюри по этой задаче