Re: подстроки

From

Oleg Khovayko ()

To

Stanislav Shwartsman

Date

2003-01-17T05:49:24Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Stanislav Shwartsman wrote:
> Hello Dmitry!
> 
> 16 Jan 03 23:57, you wrote to All:
> 
>  DK> Какой алгоритм поиска сабжа сейчас самый быстрый? 
> 
Вроде как "Алгоритм Бойера - Мура" и его разновидности.
В подавляющем большинстве случаев он производит около M/N
операций, где M - длина исходной строки, а N - искомой подстроки.

 > Где можно посмотреть
 >  DK> исходники (желательно Си)?

Ну в интернете поищите. Введите в любом поисковике
"Алгоритм Бойера - Мура" - и получите кучу вариаций.

>  Я думаю быстрее FSM (конечный автомат) вряд ли что-то сделаешь. 

БМ - побыстрее КА будет. Ибо для КА надо M операций, а для БМ - в N раз 
меньше.
>  что для произвольного текста не существует алгоритма, более быстрого,
>  чем O(длина текста) задача для средней школы.

Присоединяюсь.

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

Не существует. Кроме, возможно, гипотетического квантового алгоритма,
который очень быстро может находить запись в неупорядоченом списке.
Но я в это не верю. Да и квантового компутера еще не сделали...

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)