Решение включает в себя две основных задачи:
1. составление словаря;
2. поиск по словарю.
Поскольку размер словаря может быть весьма немалым, и заранее он неизвестен, то желательно использовать динамическую память. При указанном количестве строк и колличество слов может значительно превышать возможности сегмента (64К), так что придется структурировать. Если использование ТР не обязательно, то рекомендую взять 32-битный сомпилятор (например, FPC). Структурирование все равно весьма желательно для ускорения работы и уменьшения размеров. Структура базы данных (словаря) может быть как самой простой (слова в одном массиве of char, разделенные пробелами в алфавитном порядке), так и более сложной Например, блоки описанной струтуры, пронумерованные буквами - или парами, тройками букв.
Вот наглядная иллюстрация сказанного:
1-й способ (1):
а агат аз азот астра аська береза боб бор бочка вода воск восток дед дело дочь дочка
2-й способ с нумерацией одной буквой (2):
!а ? гат з зот стра ська !б ереза об ор очка !в ода оск осток !д ед ело очь очка
2-й способ с нумерацией двумя буквами (3):
1а ? 2г ат 2з ? от 2с тра ька 1б 2е реза 2о б р чка 1в 2о да ск сток 1д 2е д ло 2о чь чка
"?" означает слово без продолжение, только из нумерующих букв. Реально этот знак не нужен - два пробела подряд выполняют его роль.
Даже на глаз видно, что (2) выигрывает по объему по сравнению с (1).
Способ (3) на первый взгляд и сложнее, и места больше требует. Про сложность спорить не буду, но выигрыш в месте там будет заметен при бОльшем размере словаря.
Вот, примерно так.. Выбирай, что нарвится

. Или предложи свою реализацию..
Да, еще про поиск.. Его можно вести дихотомией с самого начала - либо можно хранить карту пронумерованных блоков. Внутри блока - дихотомия..

Ну, а само удаление слов - дело несложное.. ломать - не делать!

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