Структура данных для предложений слов из текстового файла

Question

Проблема: нам дан текстовый файл, содержащий много строк текста. Теперь пользователь введет несколько букв, и мы должны предложить автозаполнение на основе текста в файле, который нам дан. Допустим, файл содержит computer science is fun. computer engineering is awesome, Теперь, если пользователь вводитcom нам нужно дать как предложение computer science а также computer engineering, Если пользователь вводит is предложение должно быть fun а также awesome, Пользователь может ввести любое слово, которое может или не может быть в текстовом файле. Если этого слова нет в файле, предложения не должно быть.

Какова будет лучшая структура данных для этой проблемы.
Я знаю, что мы можем построить три, но с этим мы могли бы только предложить computer когда пользователь печатает com,

Ценю любую помощь.

Answer 1

Приготовление:

1. Читать все строки текстового файла в виде массива строк
2. Сортировать лексикографически этот массив

Запрос:

1. Получить индекс нижней границы с учетом входной строки: first
2. Увеличьте значение последнего символа вашей входной строки на 1 (если не в максимальном значении) и получите индекс нижней границы, last, для этой новой входной строки. Если ваш последний символ не может быть увеличен, используйте индекс после конца вашего массива.

Все возможные предложения находятся в отсортированном массиве между этими двумя границами, не включая последний индекс: [first, last),

Если предложений слишком много, вы можете отфильтровать их, предложив только 3 самых коротких предложения, или отсортировать по статистическим частотам.

Вы также можете распечатать количество предложений вместо того, чтобы предлагать их. Аналогично тому, как Google сообщает вам, сколько страниц соответствует вашему запросу. И тогда предлагайте строки только тогда, когда количество совпадений управляется вашим пользовательским интерфейсом.