Обобщенный быстрый поиск и хеш-функции 2

Ограничение по времени: 5 секунды
Ограничение по памяти: 4 мегабайта

Заказчику понравилось решение нашей задачи по созданию записной
книжки и он предложил нам более сложную задачу: создать простую базу
данных, которая хранит много записей вида ключ: значение. Для работы с
книжкой предусмотрены 4 команды:

ADD KEY VALUE — добавить в базу запись с ключом KEY и значением
VALUE. Если такая запись уже есть, вывести ERROR.

DDELETE KEY — удалить из базы данных запись с ключом KEY. Если
такой записи нет — вывести ERROR.

UPDATE KEY VALUE — заменить в записи с ключом KEY значение на
VALUE. Если такой записи нет — вывести ERROR.

PRINT KEY — вывести ключ записи и значение через пробел. Если такой
записи нет — вывести ERROR.

Количество входных строк в файле с данными не превышает 300000,
количество первоначальных записей равно половине количества строк (первые
N/2 команд есть команды ADD).

Длины ключей и данных не превосходят 4096. Ключи и данные содержат
только буквы латинского алфавита и цифры и не содержат пробелов.

Особенность задачи: все данные не поместятся в оперативной памяти и
поэтому придется использовать внешнюю.


Если можно, с комментариями.

0