подстроки

From

Stanislav Shwartsman (2:400/520)

To

Dmitry Kitanin

Date

2003-01-18T00:10:10Z

Area

RU.ALGORITHMS

Hello Dmitry!

17 Jan 03 21:02, you wrote to me:

 SS>>  За C*log(N) ты можешь и всю подстроку найти при условии, что
 SS>> текст (строка) был заранее обработан и проиндексирован. Вот
 SS>> только на обработку и индексацию нужно как правило больше, чем
 SS>> O(N). Поэтому если нужно искать один-два раза, то пользоваться
 SS>> всем этим уже не имеет смысла, проще просто текст просмотреть.

 DK> Меня интересовал алгоритм поиска для 1го символа с временем =const,не
 DK> зависящим от длины строки в которой ищем. Такие алгоритмы вообще
 DK> существуют? Или это в принципе не возможно? Предобработка меня не
 DK> пугает.

 Предобработкой в твоем случае может быть обычная сортировка всего текста +
 индексация по алфавиту где начинается какая буква в полученном файле.
 Тогда одну букву ты сможешь найти всего за ОДНУ операцию в независимости
 от длины строки в которой ищешь. Вот только предобработка будет тебе
 стоить O(N*logN) операций, что даже больше длины текста. И если ты
 собираешься искать свою букву меньшее кол-во раз, чем удвоенное число
 символов в тексте, в котором ищем, ты вся эта возня не имеет никакого
 смысла.

    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)