подстроки

From

Stanislav Shwartsman (2:400/520)

To

Protopopov Michael

Date

2003-01-17T10:18:43Z

Area

RU.ALGORITHMS

Hello Protopopov!

17 Jan 03 10:45, you wrote to Dmitry Kitanin:

 PM> Если загнать все N! подстрок в хэш, где N количество букв в тексте, то
 PM> можно
 PM> :)

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

 Посчитай сколько времени зайтем эта "предварительная обработка текста".
 Обычно это сортировка, а она тоже не бесплатна.

    E-mail: gate@fidonet.org.il
    Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)

Bye !
Stanislav     (AKA Night's Man)                        [Team Technion]
---
 * Origin: Gate From Another World ... From Haifa, Israel (2:400/520)