46766 (Алгоритмы поиска подстроки в строке), страница 3
Описание файла
Документ из архива "Алгоритмы поиска подстроки в строке", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "46766"
Текст 3 страницы из документа "46766"
6) Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с.
7). Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.
8). Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. – М.: Наука, 1987. – 288 с.
9). Шень, А. Программирование: теоремы и задачи [Текст]. – М.: Московский центр непрерывного математического образования, 1995.
Электронные источники.
1) http://www.ipkro.isu.ru/informat/methods/findsort/
2) http://www.delphikingdom.com/asp/viewitem.asp?catalogid=65
3) http://revolution.allbest.ru/programming/00013926_0.html
4) http://ric.uni-altai.ru/fundamental/pascal1/lab15/l15-teor.htm
5) http://www.rsdn.ru/article/alg/textsearch.xml
Приложение 1
Реализация алгоритма последовательного поиска
Приложение 2
Реализация алгоритма Рабина
Приложение 3
Алгоритм Кнута-Морриса-Пратта
Нахождение наибольшего искомого префикса.
Приложение 4
Реализация алгоритма Кнута-Морриса-Пратта
Приложение 5
Алгоритм Бойера-Мура
Реализация процедуры, вычисляющая таблицу смещений для образца p.
Приложение 6
Алгоритм Бойера-Мура
Функция, осуществляющая поиск.
Приложение 7
Реализация программного кода
d2:=length(t);
for i:= d1+p to d2 do
begin
textcolor(15);
write(t[i]);
end;
readln;
x:=x+1;
text[x]:=copy(t,1,p+d1-1);
delete(t,1,p+d1-1);
end;
until p=0;
readln;
end.
Приложение 8
Фрагмент кода тестируемой программы
Приложение 9
Общие результаты с анализов рассмотренных алгоритмов
Таблица 2
| Примечания | Алгоритмы, основанные на алгоритме последовательного поиска | Малые трудозатраты на программу, малая эффективность | Алгоритм Кнута-Морриса-Пратта | Универсальный алгоритм, если неизвестна длина образца | Алгоритм Бойера-Мура | Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. | ||||
| Время работы (мс) при длине строки ≤250 | 234 | 93 | 31 | 32 | ||||||
| Затраты памяти | нет | нет | O(m) | O(m+s) | ||||||
| Худшее время поиска | O((m-n+1)*n+1) | O((m-n+1)*n+1) | O(n+m) | O(n*m) | ||||||
| Среднее время поиска | O((m-n+1)*n+1)/2 | O(n+m) | O(n+m) | O(n+m) | ||||||
| Время на пред. обработку | нет | нет | O(m) | O(m+s) | ||||||
| Алгоритм | Алгоритм прямого поиска | Алгоритм Рабина | КМП | БМ | ||||||
33
33
33
33
33
33
33
33
33
