Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Хорошо.
word — имя команды редактора, frequency — заданная частота её использования. Получение подсказок не увеличивает frequency; сортировка подсказок лексикографическая.
Разработайте каталог строковых имён с числовыми характеристиками. Необходимо быстро искать все имена с заданным началом, ограничивать число результатов и считать общее количество совпадений.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
word — строка из 1–32 строчных латинских букв a–z.prefix — строка из 1–32 строчных латинских букв либо символ *, обозначающий пустое начало и совпадение со всеми именами.frequency — целое число от 0 до 1000000000, k — от 0 до 100000. Начальное состояние пустое.| Команда | Действие | Ответ |
|---|---|---|
PUT word frequency | Создать имя либо заменить его характеристику. | OK |
GET word | Найти точное имя. | VALUE frequency; при отсутствии NONE |
DEL word | Удалить точное имя. | OK; при отсутствии Error: NOT_FOUND |
PREFIX prefix k | Выдать первые min(k,m) совпадений лексикографически, где m — число совпавших имён. | ITEMS r, затем r строк word frequency |
COUNT prefix | Посчитать все различные имена с указанным началом. | VALUE m |
Нулевая характеристика не удаляет имя. Одно имя может быть началом другого, но это две разные записи. COUNT считает имена, а не сумму frequency. GET/PREFIX не изменяют frequency. При k=0 выдаётся ITEMS 0.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
PUT, GET, DEL, COUNT — O(L) в худшем случае, где L — длина аргумента. PREFIX — O(L + rW), где W=32 — максимальная длина имени и r — число выданных записей; просмотр всех совпадений при малом k не допускается. Память — O(суммы длин сохранённых имён + 1). Способ организации данных студент выбирает самостоятельно.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 4.8, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Ввод:
1 5 PUT cat 2 PUT car 0 PUT dog 1 COUNT ca PREFIX ca 5
Вывод:
Course work for option 4.8, created by Ivan Ivanov. OK OK OK VALUE 2 ITEMS 2 car 0 cat 2
Ввод:
1 6 PUT a 1 PUT ab 2 DEL a COUNT * PREFIX * 0 GET ab
Вывод:
Course work for option 4.8, created by Ivan Ivanov. OK OK OK VALUE 1 ITEMS 0 VALUE 2
Ввод:
1 4 PUT cat 2 PUT Cat 3 DEL car GET cat
Вывод:
Course work for option 4.8, created by Ivan Ivanov. OK Error: INPUT Error: NOT_FOUND VALUE 2