Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование

Алгоритмы поиска подстроки в строке

Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Фонарь желаний бумажный, оранжевый.
В комплекте: фонарик, горелка. Оформление упаковки - 100% полностью на русском языке. Форма купола "перевёрнутая груша" как у
87 руб
Раздел: Небесные фонарики
Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники

Федеральное министерство по образованию Государственное образовательное учреждение высшего профессионального образования «Вятский государственный гуманитарный университет» Факультет информатики Кафедра информатики и методики обучения информатике Курсовая работа Алгоритмы поиска подстроки в строке Выполнил студент III курса математического факультета Белов Денис Владимирович Проверил преподаватель кафедры информатики и методики обучения информатике Иванов С. Ю. Киров, 2006 г. Содержание. Введение Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 1.1. Основные понятия. 1.1.1 Строка, её длина, подстрока. 1.1.2. Понятие о сложности алгоритма. 1.2. Алгоритмы основанные на методе последовательного поиска. 1.2.1. Алгоритм последовательного (прямого) поиска ( he Bru e Force Algori hm). 1.2.2. Алгоритм Рабина. 1.3. Алгоритм Кнута - Морриса - Пратта (КМП). 1.4. Алгоритм Бойера – Мура и некоторые его модификации. 1.4.1. Алгоритм Боейера – Мура. 1.4.2. Модификации БМ. 1.5. Поиск подстрок с помощью конечного автомата. 1.5.1. Структура автомата. 1.5.2. Пример построения конечного автомата Часть 2. Экспериментальный анализ алгоритмов. 2.1. Суть эксперимента. 2.2. Результаты и анализ эксперимента. Заключение. Библиографический список. Введение Те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды. Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня – чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне. При этом. в готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте h ml – страницы . Работа простейшего спам – фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Все вышесказанное говорит об актуальности проблемы, затрагиваемой работой. Поставим задачу поиска подстроки в строке. Пусть у нас есть строка, состоящая из некоторого количества символов. Нам нужно проверить, входит ли другая заданная строка в данный текст, и если входит, то начиная с какого символа текста.

В данной работе мы ставим цель, выявить наиболее оптимальный алгоритм, решающий поставленную задачу поиска. Задачи данной работы: рассмотреть основные алгоритмы, решающих задачу поиска; систематизировать алгоритмы согласно используемым в них приемам; выявить эффективные, с точки зрения времени выполнения, алгоритмы. Работа содержит две основных части. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй части работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме. Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 1.1. Основные понятия. 1.1.1 Строка, её длина, подстрока. Здесь мы приводим ряд определений, которые будем использовать в изложении материала . Определение 1. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом. Определение 2. Длина строки – количество знаков в строке. Слова будем обозначать буквами латинского алфавита, напр. X=x (i-ая буква слова) принадлежит алфавиту. Le gh(X)== – обозначение длины строки. Определение 3. Слово не содержащее ни одной буквы называется пустым. Пустое слово обычно обозначают буквой L. Le g h(L)=0. Определение 4. Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX. Пример: слово ab является префиксом слова abcfa. Определение 5. Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя. Пример: слово bfg является суффиксом слова vse fbfg. Определение 6. Слово X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называют левым, а Z2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение XY. Пример: слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfro. 1.1.2. Понятие о сложности алгоритма. Целью нашей работы является найти эффективный алгоритм, однако ничего пока не было сказано о методе оценки алгоритмов. Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой. В данной работе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Мы не будем обсуждать логическую сложность разработки алгоритма - сколько «человеко-дней» нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики.

Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством переменных, элементов массивов, элементов записей или просто количеством байт . Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксперимента, подробнее об этом в части 2 данной работы. 1.2. Алгоритмы основанные на методе последовательного поиска. 1.2.1. Алгоритм последовательного (прямого) поиска ( he Bru e Force Algori hm). Самый очевидный алгоритм. Обозначим S - слово, в котором ищется образец X. Пусть m и - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,.,m- 1 в слове S; в случае равенства выводится соответствующая позиция (Листинг 1). Error: Refere ce source o fou d Очень просто, но очень неразумно. Ведь максимальное, количество сравнений будет равно O((m- 1) 1), хотя большинство из них на самом деле лишние. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату. Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку. 1.2.2. Алгоритм Рабина. Алгоритм Рабина представляет собой модификацию линейного алгоритма; он основан на весьма простой идее, которую изложим, следуя книге . «Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины . Вырежем &quo ;окошечко&quo ; размером и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в &quo ;окошечке&quo ; с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины , тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в &quo ;окошечке&quo ; и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.» (Листинг 2) Error: Refere ce source o fou d Этот алгоритм выполняет линейный проход по строке ( шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O( m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию, которая должна: 1. Легко вычисляться. 2. Как можно лучше различать несовпадающие строки. 3. hash( y ) должна легко вычисляться по hash( y.

Это выполняется вторым проходом после интерполяции переменных поэтому в шаблоны можно вставлять переменные. Для отмены интерполяции используйте '\Q'. Если вы применяете вложенные ограничители то внутренние ограничители работать не будут. ?PATERN? ?PATERN? Действие этого оператора аналогично /шаблон/ но выполняется до первого совпадения. Это удобно для поиска наличия какой нибудь строки в одном или множестве файлов. Это не очень удачный оператор поэтому в следующих версиях Перл его возможно не будет. m/PATERN/gimosx /PATERN/gimosx Поиск в строке по патерну (шаблону). В скалярном контексте возвращает логическое значение true (1) или false (''). Если строка не указана с помощью операторов '=~' или '!~' поиск ведется в строке $_ Опции: gPP Глобальный поиск. Поиск всех вхождений. iPP Сравнение не зависит от регистра (верхний или нижний) mP Строка многострочна. oP однопроходная компиляция sP однострочная строка xP используеются расширенные регулярные выражения. Если '/' ограничитель то начальное 'm' можно опустить

1. Синтез цифрового конечного автомата Мили

2. Синтез цифрового конечного автомата Мили - вариант 3

3. Проверка непротиворечивости исходных описаний конечных автоматов

4. Синтаксический разбор строк и конечные автоматы

5. Абстрактный синтез конечного автомата

6. Синтез конечного автомата для устройства управления ЭВМ
7. Поиски И.С. Тургеневым "новой" манеры в повестях 50-х годов. Повесть "Муму": её идейный смысл, образы, язык, композиция
8. Поиск подстроки в строке с помощью хеш-функции

9. Алгоритмы поиска подстроки в строке

10. В поисках системы мира

11. Поиск внеземных форм жизни

12. Поиск внеземных форм жизни

13. Гидрохимический, атмохический и биогеохимический методы поисков

14. Поиск культурных корней Американцев (Looking for cultural roots of Americans)

15. Поиски истины по роману Булгакова "Мастер и Маргарита"

16. Бургундия в поисках самоидентификации (1363-1477 гг.)

Защитный барьер для детской кровати "Polini kids", белый.
Нет ничего важнее безопасности ребенка. При переходе на подростковые кровати дети могут перевернуться и упасть во сне. Удобным и
1827 руб
Раздел: Безопасность ребенка
Фоторамка (коллаж) на 6 фото (10x15 см), 45x2x37 см.
Фоторамка на 6 фото. Размер: 45x2x37 см. Размер фото: 10x15 см. Материал: пластик.
384 руб
Раздел: Мультирамки
Форма разъемная Regent "Easy" круглая, 26x7 см.
Форма для выпечки разъемная из углеродистой стали с антипригарным покрытием. Удобная застежка. Поверхность устойчива к царапинам. Диаметр:
417 руб
Раздел: Формы и формочки для выпечки

17. Межкультурная коммуникация в электронной среде и поиск информации в сети Интернет

18. Поиск информации в www

19. Поиск клик в графах

20. Хрущев Никита Сергеевич - Поиски и решения

21. Межкультурная коммуникация в электронной среде и поиск информации в сети Интернет

22. Разработка средств оценки эффективности алгоритмов поиска и обнаружения целей прицельных радиоэлектронных комплексов
23. Методы поиска и исследований в преподавании физики
24. Человек в поисках смысла жизни

25. Поиск места расположения предприятия

26. Социализм в поисках "третьего пути"

27. Поиск общей причины неудач ppm первого рода. «Закон сохранения силы»

28. Духовная культура древней Руси в поисках святости

29. В поисках "другого"

30. В поисках утраченной цивилизации

31. В поисках новой жизни

32. Журналистское расследование: поиски жанра

Подарочный набор: визитница, ручка, брелок, арт. 140202.
Материал: искусственная кожа. Правила ухода: избегать попадания влаги. Состав: кожзаменитель, элементы металла, стекло, ПМ. В наборе:
409 руб
Раздел: Письменные наборы
Цветные карандаши Color Peps Maxi, трехгранные, 12 цветов.
Широкий грифель: плотное закрашивание, толстый карандаш удобен для самых маленьких.
371 руб
Раздел: 7-12 цветов
Телескопическая вилка.
Прикольный подарок, который рассмешит участников любого застолья. При помощи этой вилки Вы можете с невозмутимым видом «подцепить»
427 руб
Раздел: Прочее

33. Поиск положительного героя в творчестве Некрасова

34. В поисках смысла жизни (по роману Л. Н. Толстого "Война и мир")

35. Поиски смысла и правды жизни

36. Духовные и нравственные поиски личностей по повести Куприна "Поединок"

37. В поисках народного счастья (по поэме Некрасова "Кому на Руси жить хорошо")

38. Поиск клик в графах
39. Идентификация регионального политического лидера: в поисках стиля
40. Адроны, очарованные мезоны и поиски кварк-глюонной плазмы

41. В поисках пятой силы

42. В поисках определения термина «информация»

43. Экзистенциально-гуманистический подход Джеймса Бюджентала: человек в поисках самого себя

44. Усилитель мощности системы поиска нелинейностей

45. Контекстная реклама или лучший способ попасть на первую страницу поиска

46. В поисках легендарной Трои

47. Пространство и время: в поисках "естественной онтологии" знания

48. В поисках бессмертия

Набор "Стучалка", 6 гвоздиков.
Игрушка стучалка имеет вид скамейки, в которой забиты шесть разноцветных гвоздей. Все части набора деревянные, что не дает малышу
409 руб
Раздел: Стучалки, гвозди-перевертыши
Детское подвесное кресло Polini "Кокон" (цвет: оранжевый).
Подвесные детские качели яркого цвета создадут ощущение собственного укромного уголка. Надежные крепления кресла обеспечат безопасность
1225 руб
Раздел: Качели, кресла-качалки, шезлонги
Клей для дерева "Момент Столяр. ПВА Универсальный", 750 грамм.
Клей используется для склеивания, ремонта и изготовления изделий из различных видов дерева, а также ДСП, фанеры, картона и т.п. Клей
388 руб
Раздел: Для дерева

49. Поиск истины

50. Поиски новой философии математики

51. Поиск структурно-химической информации в Internet

52. Поиски альтернативных хладагентов

53. В поисках "хорошего лесопользования"

54. Историческая экология: между повседневностью и вечностью, или поиск решений на перекрестке проблем
55. Рискология. Методы верификации информации: сопоставительный анализ, метод поиска противоречий
56. Поиски оснований морали

57. Модернизация и глобализация: поиски поля равновесия

58. Поиски идеала

59. Паразиты в поисках обеда

60. В поисках идеального оружия

61. Геохимические и гидрогеологические исследования при поисках нефти

62. Электроразведка МПП при поисках трещинно-карстовых вод

63. Изучение внутренней структуры кимберлитовмещающей толщи и поиски кимберлитовых тел сейсморазведкой МОГТ и МПВ

64. Журналист в поисках информации

Часы "Камасутра".
Оригинальные часы с прямым обычным ходом. Высокое качество исполнения, веселые картинки, механизм обычный - тикающий. Диск выполнен из
958 руб
Раздел: Прочее
Кружка фарфоровая "FIFA 2018. World Cup Russia", 480 мл.
Объем: 480 мл. Материал: фарфор.
416 руб
Раздел: Кружки, посуда
Вешалки-плечики "Стандарт", комплект 10 штук, синие.
Вешалка-плечики металлическая, покрыта слоем ПВХ. Предназначена для бережного хранения одежды. Металличекая, покрытая слоем ПВХ. Размер:
333 руб
Раздел: Вешалки-плечики

65. Перспективные архитектуры генетического поиска

66. Организация функции ПОИСК в Tmemo

67. Методы поиска и анализа информации

68. Web-серверы, базы данных в Интернет, Поиск информации в Интернет, Основные системы и средства

69. Поиск в ширину на графах

70. Максимальное ускорение алгоритма поиска
71. Алгоритмы поиска в тексте
72. Поиск. Хеш-функции

73. В поисках утерянного

74. Александр I в 1812 году: поиск роли

75. Поиск зрителя документального кино, на примере фильмов режиссера В. Косаковского

76. Поиски “нравственного соглашения” между людьми как авторская задача в русской прозе 1860–1870-х годов

77. Кредитная кооперация в поисках путей развития

78. Крушение СССР и поиск новых интеграционных идей в России

79. Восхождение к ребенку: педагогика в поиске гуманистической парадигмы

80. В поисках Града Божьего: из опыта новых отечественных религиозных образований

Мягкий пол универсальный, зеленый, 60x60 см (4 детали).
4 детали - 1,5 кв.м. Пол идет в комплекте с кромками.
1080 руб
Раздел: Прочие
Рулетка для пропуска "Chrome Quadro", с карабином, 80 см.
Квадратная рулетка для бейджей из хромированного металла. С укреплённым металлическим зажимом на обратной стороне. Комбинируется со всеми
508 руб
Раздел: Бейджи, держатели, этикетки
Стиральный порошок "INDEX", универсал, 2400 грамм.
Предназначение: для стирки изделий из хлопчатобумажных, льняных, синтетических тканей, а также тканей из смешанных волокон (кроме изделий
444 руб
Раздел: Стиральные порошки

81. В поисках конкретности философствования

82. Данные о происхождении человека и поиски его прародины

83. Анализ состояния делопроизводства и поиск путей его совершенствования

84. Применение наземных гравиметрических работ на медно-порфировом месторождении Кальмакыр с целью поисков штоков гранодиорит-порфиров

85. Основные приемы поиска материала и виды вспомогательных материалов

86. Алгоритмы поиска остовного дерева Прима и Крускала
87. Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему
88. Методы поиска информации в Интернете

89. Оптимизация многомерной нелинейной функции. Слепой поиск

90. Организация хранения и поиска информации в сети Internet

91. Поиск в лабиринте

92. Поиск и сохранение информации в сети Интернет

93. Поиск информации в Интернете

94. Поиск информации в Интернете по теме "Учет движения основных средств"

95. Поиск кратчайшего пути в лабиринте

96. Поиск оптимального пути в графе

Точилка механическая "KW-Trio", с контейнером, 1 отверстие.
Точилка механическая, с контейнером, 1 отверстие, 12 мм.
1751 руб
Раздел: Точилки
Конструктор электронный "Знаток", 999 схем + школа.
Электронный конструктор "Знаток" - это 21 практическое занятие для школы и множество схем для дополнительных занятий. Основная
3856 руб
Раздел: Инженерные, научно-технические
Контейнер "Аптечка", 9 литров.
Контейнер "Аптечка" - оптимальное решение для хранения лекарств. Снабжен вкладышем для сортировки небольших предметов:
380 руб
Раздел: 5-10 литров

97. Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных

98. Хэш поиск

99. Диагноcтические карты по техническому обслуживанию и поиску неисправностей копировального аппарата "Toshiba"

100. Методы поиска отказов


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.