В качестве аргумента передаётся имя файла со множеством строк. Для каждой строки из stdin выводит "YES", если она встречается в файле, и "NO" иначе. Работа заканчивается после ввода строки "exit".

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

Бор с массивом переходов в каждой вершине. Реализован в качестве эталона для замеров времени работы всех остальных решений. Требует очень много памяти. Результаты тестирования:

Бор с односвязным списком переходов в каждой вершине. Результаты тестирования:

Бор с упорядоченным односвязным списком переходов в каждой вершине. Результаты тестирования:

Бор со сбалансированным деревом переходов в каждой вершине. Результаты тестирования:

Сет из STL, в котором храним хеши строк. Компилируется под g++. Реализован в качестве альтернативы бору для сравнения. Результаты тестирования: