MihalNik говорит, что для этого зачем-то нужны хэш-таблицы.
Но разве не будет более удобной структурой "обратный индекс по буквам" (т.е. дерево)?
Ведь при подстановке мы сначала набираем первую букву, потом вторую и затем последующие, проходя именно по дереву вариантов.