Как добиться «совпадения подстроки» за время O (n)?

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

Adana 
Izmir Adnan Menderes Apt
Addis Ababa
Aden
ADIYAMAN
ALDAN
Amman Marka Intl Airport
Adak Island
Adelaide Airport
ANURADHAPURA
Kodiak Apt
DALLAS/ADDISON
Ardabil 
ANDREWS AFB
etc..

Если я задаю условие поиска, программа должна найти строки, в которых встречается подстрока. Например, если поисковый запрос - «урадха», программа должна показать АНУРАДХАПУРА . Если поисковый запрос - «аэропорт», программа должна показать Международный аэропорт Амман Марка, аэропорт Аделаиды

Цитата из спецификаций задания: «Вы должны программировать это приложение с учетом эффективности, как если бы большие суммы данных и обработки… »

Я мог бы легко достичь этой функциональности с помощью цикла, но производительность была бы O (n). Я думал об использовании дерева , но, похоже, он работает только в том случае, если подстрока начинается с индекса 0.

Мне было интересно, какие существуют решения, которые дают производительность лучше, чем O (n)?