подстроки

From

Stanislav Shwartsman (2:400/520)

To

Dmitry Kitanin

Date

2003-01-17T17:00:58Z

Area

RU.ALGORITHMS

Hello Dmitry!

17 Jan 03 16:22, you wrote to Protopopov Michael:
 PM>> А если серьезно, то существуют и активно используются (например,
 PM>> при LZ сжатии) алгоритмы с предварительной обработкой текста,
 PM>> позволяющие, при дополнительных затратах  C*N памяти, искать
 PM>> подстроку за время C*log(N).

 DK> А если, опять же, один символ?
 DK> То есть, хочу в строке найти N-ое вхождение символа "а".
 DK> Тоже за C*log(N)?

 За C*log(N) ты можешь и всю подстроку найти при условии, что текст (строка)
 был заранее обработан и проиндексирован. Вот только на обработку и
 индексацию нужно как правило больше, чем O(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)