Поиск подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ритма Бойера-Мура состоит из двух этапов. На первом этапе строится таблица смещений для искомого образца. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. В противном случае, при совпадении символов, проводится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с соответствующими символами строки, то нужная подстрока найдена. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, то образец сдвигается на один символ вправо и снова начинается проверка с последнего символа.
Таблица смещений строится на следующих основаниях: сдвиг искомого образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то он сдвигается таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же искомая строка вообще не содержит этого символа, то образец перемещается на величину, равную его длине, так что первый символ образца накладывается на следующий символ строки. Величина смещения для каждого символа искомой строки зависит только от порядка символов в ней самой, поэтому таблицу смещений удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу из искомой строки соответствует смещение относительно последнего символа [6, 8].
Приведем пример работы алгоритма. Пусть существует алфавит из пяти символов: q, w, e, r, t и необходимо найти вхождение образца qwwqr в строке qwteeqewqrwqwwqr. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так.
qwert12505
Начало поиска.
qwteeqewqrwqwwqrqwwqr
Так как последний символ искомой строки не совпадает с соответствующим символом исходной строки, то образец смещается вправо на величину из таблицы смещений, соответствующую символу e - на 5 позиций.
qwteeqewqrwqwwqrqwwqr
Последние три символа искомой строки совпали при наложении, а четвертый символ не совпал, значит, происходит сдвиг образца вправо на одну позицию.
qwteeqewqrwqwwqrqwwqr
Снова не совпадает последний символ искомой строки, выполняется сдвиг на 2 позиции вправо.
qwteeqewqrwqwwqrqwwqr
Ещё раз выполняется сдвиг вправо на 2 позиции.
qwteeqewqrwqwwqrqwwqr
В соответствии со значением смещения для символа q выполняется сдвиг на 1 позицию.
qwteeqewqrwqwwqrqwwqr
Алгоритм считается самым быстрым алгоритмом поиска, хотя его время работы в худшем случае будет квадратным , но вероятность этого худшего варианта крайне мала. А в среднем же алгоритм показывает линейную зависимость от исходной строки.
подстрока строка алгоритм программа
2. Реализация алгоритмов
В курсовой работе были реализованы четыре алгоритма поиска подстроки в строке. Листинг программного кода алгоритма последовательного поиска представлен в Приложении А, алгоритма Рабина-Карпа в Приложении Б, алгоритма Кнута-Морриса-Пратта в Приложении В и алгоритма Бойера-Мура в приложении Г.
Тестирование алгоритмов проводилось на ПК:
Процессор Intel Atom™ CPU N455 с тактовой частотой 1.66 ГГц
1024 Мб ОЗУ
Компилятор Microsoft Visual Studio 2008.
Все реализованные алгоритмы были объединены в одно приложение, которое представляет собой интерфейс пользователя для запуска любого из представленных алгоритмов.
.1 Описание программы
Программа разработана как проект WindowsFormApplication на языке программирования C# в среде разработки Microsoft Visual Studio 2008.
Пусть дан некоторый текстовый файл, в котором необходимо найти все вхождения какого-либо фрагмента. Данную задачу можно интерпретировать как поиск подстроки в строке. Пользователю предлагается на выбор четыре алгоритма поиска: алгоритм последовательного поиска, алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта и алгоритм Бойера-Мура.
После выполнения поиска выбранным алгоритмом выводится количество тактов процессора, затраченное на поиск. И окно с результатом поиска, в котором либо сообщение о неудаче, либо номера всех вхождений искомого фрагмента в исходном тексте. Листинг программного кода приложения представлен в Приложении Д.
2.2 Порядок работы с приложением
После запуска приложения открывается основное окно программы (рис. 2.1), в котором можем наблюдать несколько элементов:
кнопка Выбрать файл поиска;
кнопка Выполнить поиск;
четыре кнопки выбора алгоритмов;
поле, для ввода искомого фрагмента.
Но все эти элементы, кроме кнопки Выбрать файл поиска, в целях защиты программы от неправильного использования, отключены до выбора текстового файла.
Рис. 2.1. Основное окно программы
При клике на кнопку Выбрать файл поиска, открывается соответствующее диалоговое окно (рис. 2.2) с фильтром текстовых документов, позволяющее открыть только файлы с расширением .txt. Фильтр нужен для защиты программы от случайной или злонамеренной попытки открыть файл, не являющейся текстовым. Выберем файл Выступление Путина.txt.
Рис. 2.2. Диалоговое окно
Далее необходимо ввести искомый фрагмент в соответствующее поле и выбрать алгоритм поиска. Введем в о?/p>