У меня есть контакты, хранящиеся в моем мобильном телефоне. Допустим, мои контакты

Ram

Hello

Hi

Feat

Eat

At

Когда я набираю письмо'A' Я должен получить все соответствующие контакты, скажем."Ram, Feat, Eat, At"

Сейчас набираю еще одну буквуT, Теперь моя общая строка"AT" Теперь моя программа должна использовать результаты предыдущего поиска"A", Теперь это должно вернуть меня"Feat, Eat, At"

Дизайн и разработка программы для этого.

Это вопрос интервью в Samsung Mobile Development

Я пытался решить сTrie data structures, Не удалось получить хорошее решение для повторного использования уже найденных результатов поиска. Я также пробовал решение со структурой данных словаря, решение имеет тот же недостаток, что и.Trie

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

Я не прошу программу. Так что язык программирования для меня несущественен.

Конечный автомат представляется хорошим решением. У кого-нибудь есть предложения?

Решение должно быть достаточно быстрым для миллиона контактов.