Интерактивная клавиатура как у навигатора

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

”Здравствуйте, уважаемое сообщество! Недавно на Хабре проскакивала неплохая обзорная статья о разных алгоритмах поиска подстроки в строке. К сожалению, там отсутствовали подробные описания каких либо из упомянутых алгоритмов. Я решил восполнить данный пробел и описать хотя бы парочку тех, которые потенциально можно запомнить. Те, кто еще помнит курс алгоритмов из института, не найдут, видимо, ничего нового для себя.”.

На первом этапе доступны все буквы и символы. Нажимаем букву П, следующий как раз шаг заблочить все кнопки на клавиатуре кроме: О,Р,А т.к. эти буквы стоят в словах:проскакивала, поиска, подстроки, подробные, парочку, потенциально, помнит, после буквы П. Второй шаг выбираем например из этих трех букв доступных на экране, букву О, доступными становиться буквы: И, Д, Т, М, из слов: поиска, подстроки, потенциально, помнит. Выбираем букву И, доступными становиться буква С из слова ”поиска” и т.д. до конца слова. Далее выводим варианты предложений с найдем словом или разблочиваем знаки пунктуации для дальнейшего по буквенного набора следующего слова. Цель этой задачи. орфографические правильно набранные слова из предложенного массива слов в предложениях.