|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 02 May 2002 18:49:01
To : Sergei Emantayev
Subject : Re: поиск подстроки в таблице
--------------------------------------------------------------------------------
> From: Sergei Emantayev <sergeie@ectel.com>
> Date: Tue, 30 Apr 2002 16:20:04 +0000 (UTC)
>
>Задачка такая: есть таблица слов, необходимо организовать поиск
>подстроки, точнее подслова в таблице. Вопрос в том, какова должна
>быть структура таблицы, чтобы поиск был максимально эффективным.
>Hапример если заранее известно, что искомое слово является префиксом
>(или суффиксом), то можно воспользоваться бинарным деревом.
>А если общий случай - поиск в середине слова? Можно взять алгоритм
>типа Морриса-Пратта, но тогда придется линейно просматривать всю
>таблицу.
>Существует ли какое-то более красивое решение?
Если памяти не жалко, а таблица статичная (словарь), то можно хранить
таблицы хэшей (т.е. 256 массивов индексов слов, содержащих данную букву,
65536 массивов индексов слов, содержащих данное буквосочентание и т.д.).
Вал. Дав.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
