Доброго всем времени суток!

Не столь давно во время отборочно-тренировочных занятий команды Украины перед Международной лингвистической олимпиадой был озвучен ряд довольно интересных задач на составление словарей. Что они из себя представляют? В общем случае задача такого плана формулируется следующим образом:

Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска слова в нем, которое определенной характеристикой.

Пример: Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска строки в нем, полностью совпадающей с строкой на входе. Очевидно, в таком случае неплохим вариантом будет стандартный словарь, в котором слова отсортированы в алфавитном порядке (тогда алгоритмом бинарного поиска мы за логарифмическое время от количества слов найдем нужную статью) (хотя на самом деле это не оптимальный вариант, но об этом чуть позже).

Позже мы решили, что операцию открытия страницы с заданным номером или статьи с заданным номером мы можем выполнять за константное время. В таком случае словарь из примера можно оптимизировать, задав функциональную зависимость между строкой и номером статьи, которая ей соответствует (или, если говорить по-людски, посчитать хеш). Тогда мы сможем искать слово за время, пропорциональное длине слова, что уже несколько круче. В принципе, используя этот подход (хеширование входных данных) может помочь нам составить необходимый словарь для любой такой задачи так, чтобы ответ искался за время, пропорциональное размеру входных данных. Поэтому всплыла еще одна характеристика — размер словаря.

Собственно, задача, которая и спровоцировала небольшой холивар, формулируется так:

Необходимо составить словарь слов так, чтобы асимптотически минимизировать время поиска слова в нем, которое подходит под заданную маску.

П.С. маска — строка из символов алфавита + специального символа (скажем, "?"), который можно заменить на любую одну букву из алфавита. П.П.С. так как задачу оптимизации времени мы вроде как решили, предлагаю вам подумать над тем, как можно ужать размеры словаря так, чтобы особо не терять во времени.