====== Вариант 4.2. Автодополнение имён ====== [[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Хорошо**. ===== Постановка задачи ===== 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