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

From

Alexander Krotoff ()

To

Valentin Davydov

Date

2002-05-02T20:24:56Z

Area

RU.ALGORITHMS

From: krotoff@such.srcc.msu.su (Alexander Krotoff)

Valentin Davydov <val@sqdp.trc-net.co.jp> wrote:
>>Задачка такая: есть таблица слов, необходимо организовать поиск
>>подстроки, точнее подслова в таблице. Вопрос в том, какова должна
>>быть структура таблицы, чтобы поиск был максимально эффективным.
>>Например если заранее известно, что искомое слово является префиксом
>>(или суффиксом), то можно воспользоваться бинарным деревом.
>>А если общий случай - поиск в середине слова? Можно взять алгоритм
>>типа Морриса-Пратта, но тогда придется линейно просматривать всю
>>таблицу.
>>Существует ли какое-то более красивое решение?

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

Как вариант (если таблица небольшая, меняется редко, а искать подстроки
нужно часто и быстро).

struct {
	int i, j, p;
	const char *str;
};
создаешь списк структур такого вида. Для каждой iой jой клетки таблицы
strlen(table[i][j]) структур. Член str каждой pой структуры указывает
на p-ый символ в строке table[i][j].
Затем этот список сортируешь по полю str (лексикографический порядок
строк). Подстроку ищешь бинарным поиском в получившемся списке, либо,
если искать нужно _очень_ быстро, строишь над структурами один из
вариантов дерева поиска (те же B-деревья).

Если нужен качественный результат - есть подстрка или нет - поля i,j,p
структуры не нужны. Если нужно находить подстроку с точностью до
клетки в таблице - не нужно поле p.

-- 
Успехов,
Саша.
--- ifmail v.2.15dev5
 * Origin: Он знал Сашу Бло. (2:5020/400)