Re: подстроки

From

Protopopov Michael ()

To

Dmitry Kitanin

Date

2003-01-17T10:45:56Z

Area

RU.ALGORITHMS

From: "Protopopov Michael" <mkp@ist.ru>

> Существуют ли алгоритмы поиска подстроки (или хотя бы 1го символа)за
время, не
> зависящее от длины строки, в которой производится поиск?
>
Если загнать все N! подстрок в хэш, где N количество букв в тексте, то можно
:)

А если серьезно, то существуют и активно используются (например, при LZ
сжатии) алгоритмы с предварительной обработкой текста, позволяющие, при
дополнительных затратах  C*N памяти, искать подстроку за время C*log(N).



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