поэтому мне нужно написать эффективный алгоритм поиска слов с пропущенными буквами в словаре, и мне нужен набор возможных слов.

Например, если у меня есть что-то, я мог бы получить эти, те, темы, там и т. Д.

Мне было интересно, если кто-нибудь может предложить некоторые структуры данных или алгоритм, который я должен использовать.

Спасибо!

РЕДАКТИРОВАТЬ: Trie слишком мало места и будет делать это слишком медленно. Любые другие идеи модификаций?

ОБНОВЛЕНИЕ: будет до двух вопросительных знаков, и когда два вопросительных знака действительно происходят, они будут появляться в последовательности.

В настоящее время я использую 3 хэш-таблицы для точного соответствия, 1 знак вопроса и 2 знака вопроса. Учитывая словарь, я хэширую все возможные слова. Например, если у меня есть слово WORD. Я хэш СЛОВО,? ORD, W? RD, WO? D, WOR ?,? RD, W? D, WO ??. в словарь. Затем я использую список ссылок, чтобы связать коллизии вместе. Так, скажем, hash (W? RD) = hash (STR? NG) = 17. hashtab (17) будет указывать на WORD, а WORD указывает на STRING, потому что это связанный список.

Время поиска в среднем одного слова составляет около 2е-6 с. Я хочу добиться большего успеха, желательно порядка 1e-9.

РЕДАКТИРОВАТЬ: я не смотрел на эту проблему снова, но это заняло 0,5 секунды для вставки записей 3м и 4 секунды для поиска записей 3м.

Спасибо!