Re: поиск подстроки в таблице

From

Valentin Davydov ()

To

Sergei Emantayev

Date

2002-05-02T18:49:01Z

Area

RU.ALGORITHMS

From: Valentin Davydov <val@sqdp.trc-net.co.jp>

>   From: Sergei Emantayev <sergeie@ectel.com>
>   Date: Tue, 30 Apr 2002 16:20:04 +0000 (UTC)
>
>Задачка такая: есть таблица слов, необходимо организовать поиск
>подстроки, точнее подслова в таблице. Вопрос в том, какова должна
>быть структура таблицы, чтобы поиск был максимально эффективным.
>Например если заранее известно, что искомое слово является префиксом
>(или суффиксом), то можно воспользоваться бинарным деревом.
>А если общий случай - поиск в середине слова? Можно взять алгоритм
>типа Морриса-Пратта, но тогда придется линейно просматривать всю
>таблицу.
>Существует ли какое-то более красивое решение?

Если памяти не жалко, а таблица статичная (словарь), то можно хранить
таблицы хэшей (т.е. 256 массивов индексов слов, содержащих данную букву,
65536 массивов индексов слов, содержащих данное буквосочентание и т.д.).

Вал. Дав.

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)