подстроки

From

Stanislav Shwartsman (2:400/520)

To

Dmitry Kitanin

Date

2003-01-16T23:49:39Z

Area

RU.ALGORITHMS

Hello Dmitry!

16 Jan 03 23:57, you wrote to All:

 DK> Какой алгоритм поиска сабжа сейчас самый быстрый? Где можно посмотреть
 DK> исходники (желательно Си)?

 Я думаю быстрее FSM (конечный автомат) вряд ли что-то сделаешь. Тем
 более, что FSM достаточно ровно одного прохода по тексту, а доказать,
 что для произвольного текста не существует алгоритма, более быстрого,
 чем O(длина текста) задача для средней школы.

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

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


    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)