Алгоритм поиска подстроки - Помощь студентам

shwan · 23.04.2012, 23:19

Задача состоит в следующем: у нас есть очень длинная исходная строка, и значительно более короткая подстрока. Алфавит достаточно маленький, 5-6 символов. Подскажите наиболее быстрый алгоритм поиска, и как возможно вообще ускорить поиск? Что можете посоветовать?
Меня интересует именно сравнение скорости работы алгоритмов, какой вы считаете более продуктивным по СКОРОСТИ.

Rin · 23.04.2012, 23:42

Двоичный алгоритм и турбо-алгоритм Бойера-Мура. Они самые быстрые, но не думай, что в реализации они будут просты.

s-andriano · 23.04.2012, 23:49

Советую для начала ознакомиться: http://ru.wikipedia.org/wiki/%D0%9F%...BE%D0%BA%D0%B8

Проблема только в том, что с точки зрения теории обычно пытаются минимизировать количество операций, например, операций сравнения. Но при этом, как правило, не учитывается одно обстоятельство: для современной динамической памяти время чтения одного произвольного байта более чем в 10 раз превосходит время чтения того же байта при последовательном чтении большого куска памяти.
Поэтому сплошное сканирование строки ассемблерной командой scans может оказаться быстрее, чем алгоритм, обеспечивающий на порядок меньшее количество сравнений.
То есть нужно сначала определиться, по какому критерию мы определяем "быстрее" - как время выполнения или как количество операций.

23.04.2012, 23:19	#1
shwan Новичок Джуниор Регистрация: 23.04.2012 Сообщений: 2	Алгоритм поиска подстроки Задача состоит в следующем: у нас есть очень длинная исходная строка, и значительно более короткая подстрока. Алфавит достаточно маленький, 5-6 символов. Подскажите наиболее быстрый алгоритм поиска, и как возможно вообще ускорить поиск? Что можете посоветовать? Меня интересует именно сравнение скорости работы алгоритмов, какой вы считаете более продуктивным по СКОРОСТИ. Мой блог о программировании http://shwanoff.ru

23.04.2012, 23:42	#2
Rin Негодник Форумчанин Регистрация: 10.11.2009 Сообщений: 880	Двоичный алгоритм и турбо-алгоритм Бойера-Мура. Они самые быстрые, но не думай, что в реализации они будут просты. Если помог, проси поставить минус. Будь оригинален!

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Алгоритм поиска	Sylar9	Общие вопросы C/C++	0	03.04.2012 12:38
A* алгоритм поиска	Nicko_mt	Помощь студентам	2	04.10.2011 02:24
алгоритм поиска	незнайка_на_земле	Помощь студентам	4	08.03.2011 10:46
Функция поиска и замены подстроки в строке типа PChar	Son	Помощь студентам	9	19.04.2010 16:06
алгоритм рабина-карпа(поиск подстроки)	kristy42	Помощь студентам	0	03.11.2009 18:41

23.04.2012, 23:49	#3
s-andriano Старожил Регистрация: 08.04.2012 Сообщений: 3,229	Советую для начала ознакомиться: http://ru.wikipedia.org/wiki/%D0%9F%...BE%D0%BA%D0%B8 Проблема только в том, что с точки зрения теории обычно пытаются минимизировать количество операций, например, операций сравнения. Но при этом, как правило, не учитывается одно обстоятельство: для современной динамической памяти время чтения одного произвольного байта более чем в 10 раз превосходит время чтения того же байта при последовательном чтении большого куска памяти. Поэтому сплошное сканирование строки ассемблерной командой scans может оказаться быстрее, чем алгоритм, обеспечивающий на порядок меньшее количество сравнений. То есть нужно сначала определиться, по какому критерию мы определяем "быстрее" - как время выполнения или как количество операций.