Re: подстроки

From

Sergey Andrianov (2:5020/1507.400)

To

Stanislav Shwartsman ()

Date

2003-01-17T23:54:04Z

Area

RU.ALGORITHMS

Здравствуй, Stanislav!

Однажды 16-Jan-03  в 23:49   Stanislav Shwartsman (2:400/520)
написал       Dmitry Kitanin    по поводу
-=-   подстроки  -=-


DK>> Существуют ли алгоритмы поиска подстроки
DK>> (или хотя бы 1го символа)за время, не зависящее от длины строки, в
DK>> которой производится поиск?

SS> Естейственно нет. Kак ты себе представляешь алгоритм поиска в СОВЕРШЕННО
SS> ЛЮБОМ тексте сколь угодно большого размера СОВЕРШЕННО произвольной
SS> строки/подстроки за постоянное время, не зависящее от длины текста ?

	Ну почему же?
	Если сначала искать подстроку во всей доступной (оперативной, дисковой, виртуальной - нужное подчеркнуть) памяти, а потом проверять найденное на принажлежность конкретной строке, то действительно, время поиска будет зависеть лишь от объема доступной памяти, но никак не от длины строки. 

                  До свидания,  в  23:51 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)