Содержание
Вариант 4.2. Автодополнение имён
Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Хорошо.
Постановка задачи
word — имя пользователя, 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.2, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Примеры
Пример 1. Подсчёт и порядок
Ввод:
1 5 PUT cat 2 PUT car 0 PUT dog 1 COUNT ca PREFIX ca 5
Вывод:
Course work for option 4.2, created by Ivan Ivanov. OK OK OK VALUE 2 ITEMS 2 car 0 cat 2
Пример 2. Имя является началом другого
Ввод:
1 6 PUT a 1 PUT ab 2 DEL a COUNT * PREFIX * 0 GET ab
Вывод:
Course work for option 4.2, created by Ivan Ivanov. OK OK OK VALUE 1 ITEMS 0 VALUE 2
Пример 3. Неверное имя
Ввод:
1 4 PUT cat 2 PUT Cat 3 DEL car GET cat
Вывод:
Course work for option 4.2, created by Ivan Ivanov. OK Error: INPUT Error: NOT_FOUND VALUE 2
