Обратная задача: поиск в таблице паттернов

From

Sergei Emantayev ()

To

All

Date

2002-05-02T13:09:01Z

Area

RU.ALGORITHMS

From: Sergei Emantayev <sergeie@ectel.com>


Теперь у меня есть обратная задача: есть таблица слов, 
на вход приходит некоторый текст. Нужно найти все слова 
из таблицы, которые находятся во входном тексте.
Можно опять же взять линейный проход по таблице + алгоритм
типа Морриса-Пратта. Но это не устраивает. 
Я посмотрел алгоритм Карпа-Рабина, там при сравнении
используются хеши. Можно было бы захешировать таблицу
и при сравнении искать хеши, но проблема в том что все
паттерны в таблице имеют разную длину. Т.е. при поиске во
входном тексте я не знаю, какой длины взять следующую
подстроку для вычисления хеша. Можно конечно брать минимальную
длину слова в таблице для хеша, мне кажется, что это
неподходящее решение.
Буду признателен за любые советы и идеи.

=====
Serge
mailto:sergeem*@yahoo.com

-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)