Поиск подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
ФГБОУ ВПО Саратовский государственный университет им. Н.Г. Чернышевского
Кафедра математической кибернетики и компьютерных наук
КУРСОВАЯ РАБОТА
Поиск подстроки в строке
Саратов, 2011
Введение
Поиск информации - одно из основных использований компьютера, и быстрый поиск точно заданной подстроки в строке является одной из самых простейших задач поиска информации. Однако эта задача является чрезвычайно важной. Данная функция встроена в различные текстовые редакторы и базы данных, что существенно ускоряет процесс поиска информации и редактирование (замену) фрагментов.
В настоящее время функции поиска подстроки в строке инкапсулированы во многие высокоуровневые языки программирования. Но стоит помнить, что стандартные функции далеко не самые оптимальные и эффективные, и если основной задачей программы является нахождение подстроки в строке, то необходимо знать принципы организации функций поиска. Также не нужно забывать, что область применения функций поиска не ограничивается одними текстовыми редакторами и базами данных. Алгоритмы поиска используются различными поисковыми роботами при индексации страниц, и от скорости нахождения необходимых ключевых слов в тексте html зависит актуальность информации. Спам-фильтр почтовых сервисов также занимается поиском в тексте писем определенных фраз, например: Миллион за час, Голосуй за Иванова!. Да даже фильтр нецензурных слов и выражений в MMORPG (massively multiplayer online role-playing game - многопользовательская ролевая онлайн-игра) является примером применения данной задачи. Все это говорит об актуальности проблемы поиска подстроки в строке.
Цель курсовой работы: изучить и произвести сравнительный анализ основных алгоритмов поиска подстроки в строке. Рассмотреть несколько практических задач на данную тему.
Задачи курсовой работы: привести основные определения по теме поиска подстроки в строке, рассмотреть применение различных алгоритмов на практике, создать программу, реализующую некоторые из этих алгоритмов.
1. Алгоритмы поиска подстроки в строке
.1 Основные определения и понятия
Определение [1]. Строка (слово) - это последовательность знаков, называемых буквами, из некоторого конечного множества, называемого алфавитом.
Определение [1]. Длина строки - количество знаков в строке.
Слова обозначаются буквами латинского алфавита, например последовательность - слово длинной , где -ая буква слова. Будем обозначать длину строки .
Определение [1]. Слово, не содержащее ни одной буквы, называется пустым. Пустое слово обычно обозначается буквой . .
Определение [1]. Слово называется префиксом слова , если есть такое слово , что . Причем само слово является префиксом для самого себя, так как найдется нулевое слово , что .
Пример: слово asd является префиксом слова asdqwe.
Определение [1]. Слово называется суффиксом слова , если есть такое слово , что . Аналогично, слово является суффиксом самого себя.
Пример: слово qwe является суффиксом слова asdqwe.
Определение [1]. Слово называется подстрокой строки , если найдутся такие строки и , что . При этом называется левым, а - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово называют вхождением в слово . Среди всех вхождений слова в слово , вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение .
Пример: слова asd и qwe являются подстроками слова ryrqwetrasdyrt.
Определение [5]. Сложность алгоритма - зависимость объема работы, выполняемой алгоритмом от размера входных данных. Причем, объем работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Т.е. сложность алгоритма - это количество времени, необходимое для выполнения алгоритма, и объем расходующейся при этом памяти. Учет памяти обычно ведется по объему данных. Время же рассчитывается в относительных единицах так, чтобы эта оценка была одинаковой для процессоров с разной частотой.
Существуют две характеристики сложности алгоритмов - временная и емкостная.
Временная сложность подсчитывается в исполняемых процессором командах: количество арифметических операций, сравнений и ссылок.
Емкостная сложность определяется объемом затраченной процессором памяти: количество переменных, элементов массивов и строк.
Эффективность алгоритма оценивается с помощью подсчета времени, затраченного программой для выполнения конкретной задачи в ходе эксперимента [5].
.2 Простейшие алгоритмы поиска подстроки в строке
.2.1 Алгоритм последовательного поиска
Алгоритм последовательного поиска - самый очевидный алгоритм. Пусть - строка, в которой выполняется поиск, а - искомое слово, и . Тогда для поиска подстроки (слова) в строке можно выполнить сравнение каждой подстроки , начинающейся с позиций , длиной . И при совпадении вывести соответствующий номер первого элемента найденной подстроки [5].
Стоит сказать, что это самый неоптимальный и неэффективный алгоритм.
В программе присутствуют два цикла, причем один из них вложенный. Внешний цикл зависит от , а внутренний в лучшем случае