Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade4:2

Вариант 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
courses/algorithms_structures/cw_2026/grade4/2.txt · Последнее изменение: — 127.0.0.1